합계 0인 정수 쌍 구하기
0을 제외한 n개의 정수가 주어졌을 때, 합이 0에 가장 가까운 숫자쌍을 구하는 sum_0(data)을 작성하세요.
[입력값]
첫 번째 줄에 n개의 정수들이 오름차순으로 주어집니다. n의 값은 따로 주어지지 않습니다.(1≤n≤100,000,000)
[결과값]
합이 0에 가장 가까운 숫자쌍을 빈 칸으로 구분하여 출력합니다. 숫자쌍은 오름차순으로 정렬하여 출력하며, 정답이 여러개일 경우 그 중 하나만 출력하면 됩니다.
[입력 예시]
-193 30 94 100 194
[출력 예시]
-193 194
풀이
- "투포인터" 알고리즘 : 1차원 배열이 있고 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 얻는 형태
- 성립하는 이유 : 배열이 정렬되어 있는 상황이어서 뒤쪽의 값들을 더하면 무조건 값이 커짐 (만일, 정렬되어있지 않다면 모든 값이 0을 포함한 자연수이어야 함)
- 시작 위치를 오른쪽으로 옮기면 값의 합이 커짐 (만일 지금의 합이 이전보다 0에 가까우면 시작 위치를 옮김)
- 종료 위치를 왼쪽으로 옮기면 값의 합이 작아짐 (만일 지금의 합이 이전보다 0에 가까우면 종료 위치를 옮김)
- 시작 위치를 오른쪽으로 옮긴 경우와 종료 위치를 왼쪽으로 옮긴 경우를 비교해서 더 0에 가까운 쪽으로 옮김
- 시작 위치(s) : - 193
- 종료 위치(e) : 194
- 둘의 합 : 1
- 첫번째 경우 : -93
- 두번쨰 경우 : 224
- -93이 0에 가까우므로 종료 위치(e)를 100으로 이동 (첫번째 경우 선택)
- 첫번째 경우 : -99
- 두번쨰 경우 : 130
- -99가 0에 가까우므로 종료 위치(e)를 94으로 이동
- 첫번째 경우 : -163
- 두번쨰 경우 : 124
- 124이 0에 가까우므로 시작 위치(s)를 30으로 이동
- 첫번째 경우 : 60
- 두번쨰 경우 : 188
- 60이 0에 더 가까우므로 종료 위치(e)를 30으로 이동하지만, 이때 종료 위치가 시작 위치보다 크지 않기 때문에 60이라는 값은 저장하지 않고 while문을 탈출
def sum_0(data):
# Implement here
return_pair = [0, 0]
# 모두 자연수여야 하는 조건이 있음
i = 0
j = len(data)-1
min_num = 100000000
while i < j :
if min_num > abs(data[i]+data[j]) :
min_num = abs(data[i]+data[j])
return_pair[0] = data[i]
return_pair[1] = data[j]
if abs(data[i]+data[j-1]) > abs(data[i+1]+data[j]) :
i = i+1
else :
j = j-1
return return_pair
def main():
'''
이 부분은 수정하지 마세요.
'''
given_data = input()
data = [int(v.strip()) for v in given_data.split()]
print (*sum_0(data))
if __name__ == "__main__":
main()
참고자료
출처 : 엘리스 아카데미, https://academy.elice.io/learn