백준 3273번 두 수의 합 Swift

https://www.acmicpc.net/problem/3273

 

내 코드

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
let target = Int(readLine()!)!

var left = 0
var right = n - 1
var result = 0

while left < right {
    if arr[left] + arr[right] == target {
        result += 1
    }
    
    if arr[left] + arr[right] < target {
        left += 1
    } else {
        right -= 1
    }
}

print(result)

---

 

Review

이중 for문을 통해 모든 경우의 수를 다 계산을 하면 시간초과가 뜨기 때문에, 투포인터를 활용하여 풀었습니다.

 

예시로 아래와 같은 배열 [1, 3, 5, 10, 12] 이 있다고 하겠습니다.
left가 가리키는 배열의 수와 right가 가리키는 배열의 수의 합이
target 과 같다면 결과에 1을 더해줍니다.

arr[left] + arr[right] 값이 target보다 작다면 left를 한 칸 이동시켜주고, 크거나 같을 경우는 right를 한 칸 이동시켜줍니다.
이 경우는 크거나 같을 경우이기 때문에 → right를 한 칸 이동시켜 줍니다.
 

다음 경우는 합한 값(arr[left] + arr[right] = 11)이 target(13)보다 작으니 → left를 한 칸 이동시켜 줍니다.
 

arr[left] + arr[right] 값이 target과 값이 같으니, 결과에 + 1을 더해줍니다.
그리고 합한 값(arr[left] + arr[right] = 13)이 target(13) 이랑 크거나 같을 경우이기 때문에 right를 한 칸 이동시켜줍니다.
 

다시 경우는 합한 값(arr[left] + arr[right] = 8)이 target(13)보다 작으니 → left를 한 칸 이동시켜 줍니다.

 

while 문 조건이 left < right 였는데, 해당 조건이 False가 되므로 while 문은 종료합니다.
투포인터를 활용하여 문제를 해결한다면 O(N)의 시간복잡도로 문제를 해결할 수 있습니다.
(정렬이 Nlog(N) 이기 때문에 최종 시간 복잡도는 Nlog(N)이 됩니다.)