[Algorithm] 두 용액 문제

이분탐색을 이용한 '두 용액' 문제 해설 및 오답노트

문제 해설

• 먼저 이 문제는 한번에 풀지 못했다..
• 일단 이중 for문으로 접근하면 풀 수 없다. N이 최대 100,000이기 때문에 이중 for문으로 풀면 시간복잡도에서 걸린다.
• 따라서 다른 아이디어를 떠올려야하는데, 탐색을 처음부터 하지않고, 먼저, 리스트를 정렬한 뒤에 양쪽에서 인덱싱을 하면서 탐색하는 '이분탐색'의 아이디어를 가지고 풀어야한다.
• 문제에서는 두수를 더했을 때 0에 수렴하는 두수를 찾으라했고, 그 두수의 조합이 두개 이상이면 최소값끼리 비교했을 때 더욱 작은 값이 있는 쪽의 조합을 리턴하도록 했다.
• 그렇다면, 먼저, O(NlogN)으로 정렬을 한뒤에, start_idx를 맨앞 0으로 잡고, end_idx를 맨끝으로 잡고 시작한다.
• 그런 다음에 더한값이 이전의 최소값으로 설정된 변수보다 작으면 최소값을 바꿔준다(인덱스를 받아가면서 한다). 이 때, 만약 더한값이 0이나오면 더이상 탐색하지 않아도 된다.start_idx가 0이고, 그말은 가장 작은 값부터 탐색하기 때문에 0이나왔을 때 후에 또 0이 나온다고해도, 이미 최소값은 이전에 찾았던 값일 것이기 때문이다.
• 이 때, 더한값이 이전의 더한값보다 크면, 점점더 값을 줄이기 위해 값이 양수면 양수쪽 인덱스(end_idx)를 하나씩 빼주고, 값이 음수면(더한값) 값을 줄이기위해 start_idx(음수쪽 인덱스)를 하나씩 더해주는 식으로 탐색을 계속한다.
• 이런 식으로 기저조건 start_idx>=end_idx까지 탐색을 무사히(?? : 0이 되는 케이스가 없던 경우) 마쳤다면, 그 때 변수에 들어있는 left, right 인덱스가 정답이되는 인덱스일 것이다.

오답 포인트

• 애초에 접근법 자체가 '이분탐색'으로 풀어야지는 했는데, 그게 양쪽에서 인덱싱을 하면서 가운데로 좁혀지는 형태라는 아이디어를 생각하지 못했다..
• 이분탐색이라고 해서 반드시 가운데에 인덱스 값을 찾고, 또 가운데 찾고 이런식이 아니라는 점을 기억하자.
• 양쪽에서 인덱싱을 줄이고, 더해나가는 방식의 풀이 꼭 기억하자.
• 그리고 마지막에 나는 이 문제를 재귀함수로 풀었는데, 문제마다 재귀함수의 제한을 걸어둔 경우가 있으므로 파이썬으로 재귀함수의 리밋을 늘리는 방법을 알아두자(이것 때문에 조금 고생함..)
  

  ---

실제 구현 코드