골5
이분탐색의 풀이 유형이 달라지는 느낌이 드는 문제였다.
해결방법은 맨 끝에서 시작해 가운데로 올 수록 0에 가까워지는 수라는 것.
즉 음수쪽에서 가장 작은 값은 가장 첫 값이고, 양수쪽에서 가장 큰 값은 가장 마지막 값이라는 것. (일단 모두 음수의 경우와 모두 양수의 경우는 생각하지 말자)
먼저 가장 왼쪽 값을 고정 시킨다. 그리고 가장 오른쪽 값을 더했을 때, 양수라면 가장 오른쪽 값 안쪽으로 0에 가까워질 여지가 있는 숫자가 존재할 수 있다.
그러므로 가장 오른쪽 값을 한칸 이동시킨다.
그리고 그 값들을 합쳤을 때 또 양수라면 계속 오른쪽 값을 이동시키고, 만약 음수라면 반대로 왼쪽의 값을 오른쪽으로 이동시킨다.
그리고 중간에 temp 값을 두어 기존에 합 값을 저장하고, 계속 갱신해나간다.
계속 이 방법을 반복해 왼쪽과 오른쪽의 합이 0이 되는 경우가 있으면 바로 그 왼쪽 오른쪽 값을 출력해주면 되고, 만약 없다면 저장해두었던 리스트를 출력하면된다.
계속해서 recursion 에러가 났다.
논리 자체에는 문제가 없었는데, 계속 찾아보다 보니 백준 시스템에는 재귀 깊이에 제한이 걸려있었다.
혹시 재귀함수를 통해 이분탐색을 푸는 사람은 꼭 이 부분을 알고 넘어가야 할 것 같다.
import sys
sys.setrecursionlimit(100000)해당 함수 호출을 통해 재귀 깊이 제한을 늘려주어야한다.
특히 이번 문제 같은 경우 이분탐색보단 투포인터 문제라 재귀의 깊이가 훨씬 깊어지게 된다. 때문에 재귀 깊이를 신경써주어야 한다.
애초에 반복문을 사용한다면 이런 문제가 발생하지 않지만, 나는 반복문 보단 재귀함수가 이분탐색 논리를 구현하는데 더 편해 재귀를 사용한다.
import sys
N = int(input())
arr = list(map(int, input().split(" ")))
ans_real = 1000000000000
sys.setrecursionlimit(100000)
ans_list = []
def solution():
# 인덱스 양 끝에서 안쪽으로 들어옴
left = 0
right = N-1
return binary_search(left, right)
def binary_search(left, right):
global ans_real, ans_list
if left >= right: # left와 right 이 만나면 return
return
ans_temp = arr[left] + arr[right]
if ans_real > abs(ans_temp): # left 와 right 의 합이 기존 저장되어있던 값보다 크면
ans_real = abs(ans_temp) # 절대값 갱신
ans_list = [arr[left], arr[right]] # 리스트 갱신
if ans_temp > 0:
return binary_search(left, right-1)
else:
return binary_search(left+1, right)
solution()
print("{} {}".format(ans_list[0], ans_list[1]))https://hellya.tistory.com/32 해당 글을 참고했다. 그림까지 넣어서 정리해두셨으니, 이 글을 보는게 더 이해하기 편할 수 있다.
