[BOJ] 1253 좋다 (Swift)

문제 링크 

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

 

문제 접근 

N 개의 수 중 어떤 수가 다른 두 수의 합이 되는 숫자의 개수를 찾아야 한다. 

주의할 점은, 각 수가 가질 수 있는 숫자의 범위가 절댓값 1,000,000,000이라는 것이다. 

물론 주어진 수를 하나씩 비교하며 답을 찾을 수 있을 것이다. 그치만 그 방식으로 실행한다면 시간이 엄청 오래 걸릴 것이다.

그럼 시간을 줄일 수 있는 방법을 찾아야 한다. 

 

일단 이 문제는 숫자의 순서를 유지할 필요가 없다. 그럼 정렬을 하는 방법을 생각할 수 있다. 

오름차순으로 정렬했을 때, 앞에서부터 두 개의 숫자를 더해서 답을 찾고자할 수 있다. 하지만 이 경우에도 최악의 경우 시간복잡도가 O(N^3)이 될 것이다.

 

두 수를 얻기 위한 두 개의 포인터가 있다고 할 때, 하나는 앞에서부터, 다른 하나는 뒤에서부터 탐색한다면 이분탐색 방법으로 구할 수 있다.

 

문제 풀이

1. N개의 수를 오름차순으로 정렬한다. 

2. N개의 수를 하나씩 확인하며 "좋은 수"인지 확인한다. 

3. "좋은 수" 인지 확인하는 방법은 이분탐색 알고리즘을 이용한다. 

 

전체 코드

import Foundation

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

while index < n {
    // "좋은 수"인지 확인할 숫자
    let currentNum = arr[index]

    // 포인터 두 개
    var (st, ed) = (0, n - 1)
    while st < ed {
        let sum = arr[st] + arr[ed]

        // sum이 currentNum 보다 클 때 or 더하는 값 중 더 뒤의 수가 currentNum 일 떄
        if sum > currentNum || ed == index {
            ed -= 1
        }
        // sum이 currentNum 보다 작을 때 or 더하는 값 중 더 앞의 수가 currentNum 일 떄
        else if sum < currentNum || st == index {
            st += 1
        }
        // sum이 currentNum과 같을 때 => "좋은 수"
        else {
            answer += 1
            break
        }
    }
    index += 1
}

print(answer)

 

 

아이디어만 생각할 수 있다면 그다지 어려운 문제는 아닌 것 같다. 찾고자하는 것이 "두 수의 합이 기준과 같은지"인데, 탐색을 할 때 두 수의 합이 기준보다 클 때, 작을 때, 같을 때로 경우를 나누어 볼 수 있다는 것을 인지하니 이분탐색으로 풀 수 있음을 알아챌 수 있었다.  

(처음에는 수에 음수는 없는 줄 알고 `currentNum`보다 앞에 있는 숫자들만 탐색했었다.. 조건을 잘 읽자)