-
백준 2473 세 용액Algorithm/BOJ 2021. 5. 3. 10:06728x90
출처: 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개를 한 번에 다 움직이려고 했는데 이렇게 하면 모든 케이스를 다 생각해줄 수가 없게된다..!!
'Algorithm > BOJ' 카테고리의 다른 글
백준 14891 톱니바퀴 (0) 2021.05.13 백준 17609 회문 (0) 2021.05.03 백준 14719 빗물 (0) 2021.05.02 백준 1922 네트워크 연결 (0) 2021.04.30 백준 1981 후위 표기식 (0) 2021.04.26