2470

날짜 : 2022. 11. 12

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num.sort()
i = 0 # 처음
j = len(num)-1 # 끝
dist = num[0] + num[-1] # 기본 거리값
x, y = num[0], num[-1]

while i < j: # 교차하면 탈출
    if num[i] + num[j] == 0: # 합이 0이면 무조건 탈출
        x, y = num[i], num[j]
        break
    if abs(dist) > abs(num[i] + num[j]): # 값 갱신
        x, y = num[i], num[j]
        dist = num[i] + num[j]
    if (num[i] + num[j]) > 0 : # 값 비교 후 i, j 중 이동할 인덱스 정하기
        j -= 1
        #print("j 감소")
    else: 
        i += 1
        #print("i 증가")
    #print(num[i], num[j])

print(x, y)

 

풀이

- 이진탐색(Binary Search)을 이용해서 해결하는 문제였다.

- 이를 간과하고 배열을 2개 만든 다음 서로 교차하는 방식으로 진행했지만 당연하게도 시간초과가 발생했다.

- 그래서 이진탐색 개념을 확인 후 구현했고, 합이 0이 되는 경우를 제외한 모든 경우의 수를 탐색하는 것을 구하는 과정에서 꽤 많은 고민이 필요했지만 해결할 수 있었다.

- 다만, 값을 생긴하는 것과 i, j를 이동하는 것을 정하는 과정을 간과했다는 점에서 아직 많이 부족한 것이 느껴진다.

 

 

알게된 점

- Binary Search

 

 

참고 사이트

- https://velog.io/@kimdukbae/이분-탐색-이진-탐색-Binary-Search

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)