Baekjoon2473_세 용액

문제

풀이

일단 내 풀이는 틀렸다. 이분 탐색을 이용하여 start에 위치한 값과 end에 위치한 값, 그리고 그 둘의 중간에 있는 mid에 위치한 값의 크기가 가장 작을 때를 찾는 로직을 짰으나 처참히 틀리고 말았다. 여러 반례들을 찾아가며 확인했을 때 전부 답을 출력했기에 2시간 이상을 내가 맞다 우기며 코드를 계속 잡아 뜯어보았지만 마지막에 찾은 반례가 처참히 내 코드를 부쉈다.

틀린 코드

import sys 
input = sys.stdin.readline

n = int(input())
num_list = list(map(int,input().split()))
num_list.sort()

l, r = 0,n-1
check = 4e9 

answer= []
mid = (l+r) // 2


while l < r:
        if l == mid:
            l = mid
            mid = (l+r) // 2  
        if r == mid:
            r = mid
            mid = (l+r) // 2
        temp = num_list[l] + num_list[r] + num_list[mid]
        if abs(temp) < abs(check):
            if temp == 0:
                answer = [num_list[l],num_list[r],num_list[mid]]
                break
            
            check = temp
            answer = [num_list[l],num_list[r],num_list[mid]]
        if r - l < 3:
            break
        if temp < 0:
            l = l+1
        else:
            r = r-1

    answer.sort()
    print(answer[0], answer[1],answer[2])
        

이후 풀이

다시금 문제를 찬찬히 읽어보고 다른 사람들의 코드를 참고하여 다시 코드를 작성했다. 이번에는 투 포인터를 이용해서 문제를 풀었다. 총 3가지 값 중 값 한 개를 고정시켜두고 투 포인터 방식으로 문제를 푸니 생각보다 쉽게 풀렸다. 항상 처음에 떠올린 방법에 매몰되지 말고 문제를 넓게 보는 시각을 갖자!

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
num_list = list(map(int,input().split()))
num_list.sort()

answer = []
check = 4e9
if n == 3:
    num_list.sort()
    print(num_list[0], num_list[1], num_list[2])
for i in range(n-2):
    third = num_list.pop()
    start, end = 0, len(num_list)-1
        
    while start != end:
        temp = num_list[start] + num_list[end] + third
            
        if check >= abs(temp):
            check = abs(temp)
            answer = [num_list[start], num_list[end], third]
                
        if temp < check:
            start += 1
        else:
            end -= 1
        if check == 0 :
            break
answer.sort()
print(answer[0], answer[1],answer[2])