[TIL] 백준 2467 - 용액 ( python )

📌 문제 탐색하기

N = 전체 용액의 수

solutions = 용액의 특성값 저장하는 배열

 

산성 용액과 알칼리성 용액 각각에 대해 정수값(산성: 양수, 알칼리: 음수)이 있습니다.
두 개의 서로 다른 용액을 혼합했을 때 그 합이 0에 가장 가까운 두 용액을 찾는 것이 핵심입니다.

 

찾은 두 용액의 특성값을 오름차순으로 출력해야 합니다.

산성 용액끼리 혹은 알칼리성 용액끼리 혼합하는 경우도 고려해야 합니다.

 

2 ≤ N ≤ 100,000

-1,000,000,000 ≤ 각 용액의 특성값 ≤ 1,000,000,000

가능한 시간복잡도

1. 브루트 포스(완전 탐색):
   
   • 모든 가능한 쌍을 계산하면 N(N-1) / 2 입니다.
   • N이 최대 100,000이면 대략 100,000 * 99,999 = 10^10 이고, 2로 나누면 5 * 10^9 정도의 연산이 필요합니다.
   • 약 50억 번의 연산이 필요하므로 1초 내에 불가능합니다.
2. 이진 탐색
   
   • 한 용액을 고정하고 나머지 용액에서 -해당 용액에 가장 가까운 값을 찾기 위해 이진 탐색을 수행합니다.
   • 각 고정 용액마다 O(log N) 연산이 필요합니다.
   • 전체적으로 O(N log N) 시간이 걸립니다.
3. 투 포인터 
   • 입력이 정렬되어 있기 때문에, 왼쪽과 오른쪽에 동시에 탐색하면 한 번의 선형 스캔으로 해결 가능합니다.
   • O(N) 시간에 해결됩니다.
   • N이 최대 100,000인 경우, 100,000번의 연산을 하므로 1초 내에 가능합니다.

알고리즘 선택

입력이 이미 정렬되어 있기 때문에,
가장 작은 값(음수)과 가장 큰 값(양수)에서 시작해서 0에 가까워지는 방향으로 포인터를 이동시키면 됩니다.

직관적이고, 각 단계에서 현재 상태를 쉽게 이해할 수 있는 투 포인터 알고리즘을 사용하겠습니다.

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• left = 0(배열의 가장 왼쪽), right = N - 1(배열의 가장 오른쪽)로 설정합니다.
• 각 용액의 합이 0과 가까운 수를 저장할 변수 sum을 설정합니다.
• sum은 매우 큰 값으로 초기화합니다.
• 각 용액의 값을 저장하는 변수 pair을 설정합니다.
• pair에는 초기 두 용액을 저장합니다.
• 각 용액의 합이 0에 가까운 값이 나올 수 있도록 반복문을 반복합니다.
  
  • left < right 될때까지 반복문을 반복합니다.
  • 각 용액의 합( solutions[left] + solutions[right] )을 mix에 저장합니다.
  • 절대값 mix 가 절대값 sum보다 작을 때
    
    • sum값을 mix로 갱신합니다.
    • pair에 두 용액의 값( solutions[left], solutions[right] )을 저장합니다.
  • 만약 mix == 0이면 최적 해이므로 바로 종료합니다.
  • mix < 0 , 왼쪽 포인터를 오른쪽으로 한 칸 이동하면 됩니다. ( 합을 크게 만들어 0에 더 가깝게 만듭니다.)
    • left += 1
  • mix > 0 , 오른쪽 포인터를 왼쪽으로 한 칸 이동하면 됩니다. ( 합을 작게 만들어 0에 더 가깝게 만듭니다.)
    • right -= 1
• pair에 저장된 두 용액의 특성값을 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

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

left, right = 0, N - 1
sum = float('inf')
pair = (solutions[left], solutions[right])

while left < right:
    mix = solutions[left] + solutions[right]
    
    if abs(mix) < abs(sum):
        sum = mix
        pair = (solutions[left], solutions[right])
    
    if mix == 0:
        break
    
    if mix < 0:
        left += 1
    else:
        right -= 1

print(pair[0], pair[1])