[Swift Algorithm] 두 수의 합 BOJ #3273

문제 설명

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

 

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

입출력 예제

입력

9
5 12 7 10 9 1 2 3 11
13

 출력

3

 

내 문제 풀이

import Foundation

let count = Int(readLine()!)!
let nums = readLine()!.components(separatedBy: " ").map({Int($0)!}).sorted()
let sum = Int(readLine()!)!
var max = nums.count

var result = 0

for i in 0..<nums.count-1 {
    if i < max {
        for j in (i+1..<max).reversed() {
            if i < j {
                if nums[i] + nums[j] == sum {
                    result += 1
                    max = j
                    break
                }
            }
        }
    }
}

print(result)

• 이분탐색을 이용하여 풀이했다.
• 효율적인 탐색을 위하여 먼저 입력받은 숫자들을 오름차순으로 정렬했다.
• 2중 for문을 사용하는데, 바깥 for문에서는 순서대로 검사를 하고
  안쪽 for문에서는 뒤에서부터 반대로 검사했다.
• 어차피 한 번 쌍이 맺어진 숫자는 더이상 다른 숫자와는
  쌍이 될 수 없기 때문에 (중복되는 수는 입력되지 않기 때문)
  안쪽 for문에서, 쌍이 맺어짐을 확인할 때마다 max를 바꿔주어 쓸데없는 반복은 피했다.
• 계속 쌍을 맺으며 max를 낮은 숫자로 바꿔주다보면 언젠가 i보다 작거나 같아질 수 있기 때문에,
  i < max 라는 조건을 두 번째 for문 전에 걸어주었다.

 

💡 피드백

• 처음엔 이분탐색으로 풀 생각을 못하고, 그냥 순차대로 검사하는 for문을 2중으로 사용했는데,
  그렇게 하니까 자꾸 시간 초과로 통과하지 못했다.
• 구글링해서 이분탐색으로 풀어야한다는 점을 알아내어 풀었는데,
  이 문제를 잊을 즈음에 다시 풀어서 이분탐색을 정확히 익혀봐야겠다.

 

---

 

문제

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