[백준/Python] 2467 용액

 

📌 문제 탐색

• 길이 N(2 ≤ N ≤ 100,000)의 용액 배열
• 각각의 용액은 산성 또는 알칼리성
  • 산성 : 1부터 1,000,000,000까지의 양의 정수
  • 알칼리성 : -1부터 -1,000,000,000까지의 음의 정수
• 두 가지 용액을 섞으면 두 용액의 특성값의 합이 새로운 용액의 특성값이 됨
• 두 용액을 섞어 특성값이 0에 가장 가까운 혼합 용액을 만들어 낼 때를 찾아서, 두 용액 각각의 특성값 구하기
• 산성 용액과 알칼리 용액을 반드시 각각 하나씩 쓸 필요 없음에 주의

주어진 조건을 보면 용액의 수가 최대 100,000개이므로, 단순히 모든 용액 쌍을 계산하는 방식은 O(N^2)으로 시간이 매우 오래 걸릴 수 있다. 용액의 리스트가 오름차순으로 정렬되어 있으므로, 리스트의 가장 왼쪽에는 가장 작은 용액, 가장 오른쪽에는 가장 큰 용액이 존재한다. 두 값의 합이 0에 가까워지기 위해선, 한쪽 값이 크면 다른쪽 값은 그만큼 작아야 한다. 즉, 이 특성을 활용해 리스트의 양 끝에서부터 값을 비교해나가면, 불필요한 연산을 줄일 수 있다.

 

리스트의 양 끝에서부터 값을 비교하기 위해 포인터 두 개를 사용해서, 양 끝을 가리키도록 한다. 포인터가 가리키는 두 용액의 합이 0보다 크다면, 두 값의 합을 더 작게 만들기 위해 오른쪽 포인터를 왼쪽으로 이동하고, 그렇지 않다면 합을 더 크게 만들기 위해 왼쪽 포인터를 오른쪽으로 이동시킨다. 

 

이렇게 투포인터를 활용하면 리스트를 한 번만 탐색하므로 시간복잡도는 O(N)이 되고, 충분히 시간 내에 문제를 해결할 수 있다.

 

+)

당장 떠오른 방법은 위와 같이 투포인터를 활용한 방법이라 투포인터로 풀었지만, 하나의 용액을 고정하고 나머지 용액 중에서 더해서 0에 가까운 값을 찾기 위한 방법으로 이분탐색으로도 풀 수 있다. 이분탐색으로 푸는 경우, 리스트의 각 용액을 하나씩 고정하는 데 O(N)의 시간복잡도, 각 용액 고정 후 나머지 용액에 대한 이분탐색에 O(logN)의 시간 복잡도로, O(NlogN)의 시간복잡도가 소요된다.

 

---

📌 코드 설계

1. 용액의 개수 N을 입력받는다.
2. N개의 용액 리스트(liquids)를 입력받는다. (이미 오름차순 정렬된 상태로 입력이 들어옴)
3. 포인터 두개(left, right)를 리스트의 양 끝에 설정한다.
4. 포인터 두개가 가리키는 값의 합이 0에 가장 가까운지 확인하며, 포인터를 조정한다.
   1. 현재 포인터가 가리키는 값의 합이 가장 0에 가깝다면, best_value, best_value_left, best_value_right을 갱신한다.
   2. 현재 포인터가 가리키는 값의 합이 0보다 작다면, left에 1을 더한다.
   3. 현재 포인터가 가리키는 값의 합이 0보다 크다면, right에 1을 뺀다.
5. 최종적으로 0에 가장 가까운 두 용액의 값을 출력한다.

 

📌 시도 회차 수정 사항

1회차

best_value = 1e9

탐색 중 찾아낸 가장 0에 가까운 특성값을 저장하는 변수(best_value)를 1e9로 설정했다. 문제 조건 상 일부 테스트케이스의 경우 실제 0에 가장 가까운 특성값이 1e9보다 크거나 같은 값이 될 수 있기 때문에 조건 상 걸리지 않는 값인 1e10으로 수정하여 정답을 받았다. 좀 더 정확하게 하려면 best_value는 abs(liquids[0] + liquids[n-1])로 초기화 하고, best_value_left, best_value_right를 각각 liquids[0], liquids[n-1]로 수정해주는 것이 좋을 것이다.

---

📌 정답 코드

N = int(input())
liquids = list(map(int, input().split()))

left, right = 0, N-1
best_value = abs(liquids[left]-liquids[right])
best_value_left, best_value_right = liquids[left], liquids[right]

while left < right:
  current_value = liquids[left] + liquids[right]
  if abs(current_value) < abs(best_value):
    best_value = current_value
    best_value_left, best_value_right = liquids[left], liquids[right]

    if best_value == 0:
      break
  
  if current_value < 0:
    left += 1
  else:
    right -= 1

print(best_value_left, best_value_right)