백준 2473 세 용액

출처: www.acmicpc.net/problem/2473

분류: 투포인터

---

접근방식

두 개의 포인터로 찾는 문제가 일반적인데 이번엔 세 개의 합을 찾아야 했습니다.

먼저 하나를 정해놓고 나머지 부분에서 일반적인 투포인터 방식으로 접근하면 해결할 수 있습니다.

처음에 정한 것 외에 2개가 더 필요하니 0..<n-2 까지 반복합니다.

 

해결방법

// MARK: 2473 세 용액

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

var closeSet = [Int]()
var closeZero = 10_000_000_000

loop: for i in 0..<n-2 {
    var start = i+1
    var end = n-1
    
    while start < end {
        let sum = arr[i] + arr[start] + arr[end]
        if abs(sum) < closeZero {
            closeZero = abs(sum)
            closeSet = [arr[i], arr[start], arr[end]]
        }
        
        if sum == 0 {
            break loop
        } else if sum > 0 {
            end -= 1
        } else {
            start += 1
        }
    }
}

print("\(closeSet[0]) \(closeSet[1]) \(closeSet[2])")

 

배운점

처음에는 sum이 0보다 작을 때 p1, p2가 붙어있으면 p2를 아니면 p1을 움직여서 3개를 한 번에 다 움직이려고 했는데 이렇게 하면 모든 케이스를 다 생각해줄 수가 없게된다..!!