코드

n = int(input())
arr = list(map(int, input().split()))

# 최댓값 생성
INF = int(100e9)

# 두 용액을 담을 리스트
target = []

def solution(arr, target):
    
    # 두 용액의 합을 담을 변수
    tot = INF
    
    # 반복문을 이용하여
    # i번째 용액부터 n-1번째 용액까지
    # 각각 용액 둘의 합을 구해서
    # 0에 가장 가까운 값을 이진 탐색으로 찾음
    for i in range(n-1):
        
        # 시작 용액은 반복시 마다 바뀜
        start = i+1
        end = n-1
        
        # 현재 용액
        now = arr[i]
        
        while start <= end:
            mid = (start + end) // 2
            
            # 현재 용액 + 이진 탐색으로 찾은 용액
            # 두 용액의 합을 담을 임시 변수
            # arr[mid] : 이진 탐색으로 찾은 용액
            tmp = now + arr[mid]
            
            # 합이 0이면 값을 찾았으므로
            # 함수를 종료하고 target을 반환함
            if tmp == 0:
                target = [arr[i], arr[mid]]
                return target   
            
            # tot가 값이 abs(tmp)보다 크다면
            # abs(tmp)로 업데이트
            # target에 두 값을 넣고 반환
            # 0에 가장 가까울 것이므로 절댓값을 취해줌
            if tot > abs(tmp):
                tot = abs(tmp)
                
                target = [arr[i], arr[mid]]
            
            if tmp < 0:
                start = mid + 1
            else:
                end = mid - 1
    return target
    
print(*solution(arr, target))

문제 해설

이진 탐색 문제.

백준 2470 - 두 용액 링크의 문제와 거의 똑같은 문제이나, 카테고리 분류가 링크의 문제는 투 포인터에 있고, 이번 문제는 이진 탐색에 있어서 이진 탐색으로 풀었다.

for문에 while문까지 사용하여 이진 탐색을 구현하는 문제는 처음 접해봐서 그런지 이 로직을 생각하는게 생각보다 힘들었다. 그래도 이후 로직은 문제를 꼼꼼히 읽어보면 천천히 구현할 수 있었으나, 함정은 다른 곳에 있었다.

주피터 노트북에서 예시를 풀어도 항상 정답과 일치하였고, 참고 코드를 봐도 코드 자체는 다르더라도 로직이 다른 곳은 없는데 ‘‘틀렸습니다’’ 만 무한으로 나오는 걸 보면서 1시간 정도는 시간을 잡아먹혔다. 이유는 아래와 같았다.

난 이때까지 INF라는 무한대의 값을 설정할 때 항상

INF = int(1e9)

위와 같이 생성하였다. 이는 곧 1000000000이라는 숫자이다. 즉, 10억이라는 엄청 큰 숫자이고 주어지는 범위가 이를 넘기는 경우는 거의 없으니 항상 이 값을 지정하였다. 허나, 이 문제는 이 범위로는 만족할 수 없는 문제였다.

용액의 범위가 -10억 ~ +10억 사이 이므로 두 용액 합의 절댓값이 10억을 넘기는 경우가 허다하게 발생할 수 있었다. 이렇게 큰 범위를 간과하고 문제에 접근한 채로 시간만 잔뜩 잡아먹은 것이다.

이 문제를 통하여 어떤 문제를 접하더라도 문제에서 주어지는 조건을 하나 하나 꼼꼼히 따져보는 버릇이 필요하다는 것을 절실히 깨달았다. 앞으로 모든 문제를 꼼꼼히 천천히 읽는 습관을 가져야겠다.

댓글남기기

참고