본문 바로가기

투포인터4

[Swift][투포인터] 백준 3273번 (두 수의 합) 요구능력 투 포인터 문제풀이 이전의 수고르기에서는 두 수의 차를 구하는것이었다. 그래서 기존에 내가하던 방식의 투포인터로 맨앞에서부터 start와 end를 함께 올려갔는데, 이 문제의 경우에는 합을 구하는거라 위에 방식대로하면 합이 계속해서 커질 수 밖에 없기 때문에 비교가 되지 않는다. 그래서 맨앞쪽과 맨뒤쪽에 포인터를 두고 비교를 해주었다. 후기 투포인터는 유형이 다양한거같다. 코드 let n = Int(String(readLine()!))! var arr = readLine()!.split(separator: " ").map{Int(String($0))!}.sorted() let x = Int(String(readLine()!))! var left = 0 var right = n - 1 var re.. 2022. 5. 31.
[Swift][투 포인터] 백준 2230번 (수 고르기) 요구능력 투 포인터, 정렬 문제풀이 포인터가 가리키고있는 위치의 값끼리 차를 구하면된다. 중요한점은 정렬을 해주지 않으면 투포인터가 성립되지 않는다. 그리고 diff >= m이 되면 우리는 최소의 차이를 구하는 것이므로 정렬되어있기 때문에 뒤로갈수록 차이는 더 커져서 볼 필요없이 break해줬다. 후기 투포인터의 응용(?)문제 코드 let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nm[0] let m = nm[1] var arr = [Int]() for _ in 0.. 2022. 5. 20.
[Swift][Two-Pointer] 백준 1644번 (소수의 연속합) 요구능력 투포인터, 에라토스테네스의 체 문제풀이 우선, 에라토스테네스의 체를 이용해서 소수를 판별해주었다. 에라토스테네스의 체를 이용해서 소수를 판별할 때 주의할 점이 있는데, 나는 처음에 에라토스테네스의 체의 배열 개수를 n + 1로 두었다가 97%에서 런타임에러가 나서 최대인 4000001로 설정했다. 그리고 투포인터를 이용해서 end를 증가시키면서 end가 소수인경우 더해줬다. 이렇게 하면 연속적으로 소수만 부분합을 구하게된다. 가장 중요한점은 start가 소수여야된다는 것이다. 자기자신이 소수가아니라면 continue로 넘겨주었다. 후기 투포인터를 살짝 꼬아낸거같다. 코드 import Foundation let n = Int(String(readLine()!))! var arr = Array(re.. 2022. 5. 9.
[Swift][Two-Pointer] 백준 1806번 (부분합) 요구능력 투포인터 문제풀이 연속된 수들의 부분합이라는 부분에서 투포인터가 생각났다. 이 문제에서 핵심이라고 느껴지는 부분은 투포인터를 이용해서 부분적인 합을 구했을 때 그 합이 s를 넘어가게 되는 그 시점이 최소길이라는 것이다. 그 이상으로 넘어가버린다면, 최솟값이 될 수 없다. 예를 들어서 1 2 3 2 5라는 수가 있는데, s가 3이다. 그렇다면 start index가 0에있고, end index가 1에 있다면, 우선은 그 때가 최소인 부분이다. 만약 더 탐색하게되서 1 2 3까지 탐색하면 문제의 조건인 s이상은 만족을 하지만, 최소길이는 될 수 없다. 그래서 합이 s보다 작을 때까지만 while문을 돌려준 것이다. 후기 투포인터의 개념을 알고있다면 풀만한 문제인것같다. 코드 import Founda.. 2022. 5. 9.