백준 2470번 풀이 - 파이썬(Python) (정렬 / 두 포인터)

난이도: 골드5

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

 

 

---

나의 풀이 ( 두 포인터 사용)

n = int(input())
array = sorted(list(map(int, input().split())))

# 포인터 두 개(left, right)와 최소일 때의 값, 위치를 기억하는 변수들(min, min_left, min_right)을 선언
left = 0
right = n - 1
min = abs(array[left] + array[right])
min_left = left
min_right = right


while left < right:
	# 용액의 합이 0이면 기록 후 즉시 종료
    if abs(array[left] + array[right]) == 0:
        min = abs(array[left] + array[right])
        min_left = left
        min_right = right
        break
	# left, right의 차이가 2 이상일 때(이동 시 겹치지 않을 때)
    # left 또는 right가 이동한 경우, 각각의 값을 비교하여 어느 포인터를 이동할지 결정
    if abs(array[left] + array[right - 1]) < abs(array[left + 1] + array[right]) and (right - left) >= 2:
		# 이동한 것이 최소라면, 해당 정보 기록
		if abs(array[left] + array[right - 1]) < min:
            min = abs(array[left] + array[right - 1])
            min_left = left
            min_right = right - 1
        right -= 1
    # 위와 로직 동일
    elif abs(array[left] + array[right - 1]) >= abs(array[left + 1] + array[right]) and (right - left) >= 2:
        if abs(array[left + 1] + array[right]) < min:
            min = abs(array[left + 1] + array[right])
            min_left = left + 1
            min_right = right
        left += 1
    # left, right 차이가 1이라면, 같게 만들어 다음 반복문이 실행되지 않게 함
    else:
        right -= 1
    

print(array[min_left], array[min_right])

두 포인터로 풀었다.

논리가 틀리진 않았으나, 굉장히 복잡하다.

복잡했음에도 끝까지 구현한 것은 스스로 만족스러웠다.

남의 풀이가 궁금하다.

 

 

 

 

 

남의 풀이1 (두 포인터 사용)

# input 입력 받기
n = int(input())
solution = list(map(int, input().split(' ')))

# 정렬하기
solution.sort()

# 이중포인터 설정
left = 0
right = n-1

answer = 2e+9+1 # 기준값
final = [] # 정답

# 투포인터 진행
while left < right:
    s_left = solution[left]
    s_right = solution[right]

    tot = s_left + s_right
    # 두 용액의 합이 0과 가장 가까운 용액을 정답에 담아주기
    if abs(tot) < answer:
        answer = abs(tot)
        final = [s_left, s_right]
	
    # 두 용액의합이 0보다 작다면 왼쪽의 값을 늘려 조금 더 0에 가깝게 만들어준다
    if tot < 0:
        left += 1
    # 반대로, 두 용액의 합이 0보다 크다면 오른쪽의 값을 줄여서 조금 더 0에 가깝게 만들어준다
    else:
        right -= 1

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

전체적인 논리는 비슷하지만,

이동 시 값을 비교한 것이 아니라, 논리를 통해 접근했다.

두 용액의 합이 0보다 작다면, left를 +=1 하고

0보다 크다면, right를 -=1 했다.

굳이 left +=1, right -=1 한 경우를 비교한 후 움직일 필요가 없었던 것이다.

 

 

 

 

 

남의 풀이2 (이분 탐색 사용)

출처 : https://latte-is-horse.tistory.com/316

n = int(input())
arr = sorted(map(int, input().split()))  # 정렬된 용액들


def binary_search(s, target):
    global arr
    res = n
    start, end = s, n - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= target:
            res = mid
            end = mid - 1
        else:
            start = mid + 1
    return res


def solution():
    global arr
    v1, v2 = 0, 0
    best_sum = 10 ** 10
    for i in range(n):
        # 이분 탐색 수행: 현재 위치(i) 이후의 용액에서 탐색, 찾는 값은 (현재 용액 * -1)
        res = binary_search(i + 1, -arr[i])
        
        # 찾은 용액의 왼쪽 용액 확인
        if i + 1 <= res - 1 < n and abs(arr[i] + arr[res - 1]) < best_sum:
            best_sum = abs(arr[i] + arr[res - 1])
            v1, v2 = arr[i], arr[res - 1]

        # 찾은 용액 확인
        if i + 1 <= res < n and abs(arr[i] + arr[res]) < best_sum:
            best_sum = abs(arr[i] + arr[res])
            v1, v2 = arr[i], arr[res]
    
    print(v1, v2) # i 번째 용액을 확인할 때 i + 1번 용액부터 확인하기 때문에 항상 v1 <= v2 이다.


solution()

이분 탐색으로 풀었다는 것이, 직관적인 논리로 다가오지는 않는다.

하지만, 아래와 같은 사고 흐름이라면 직관적이다.

 

1. 브루트포스(전체 경우의 수에 대해 탐색)를 생각

2. 시간 복잡도를 고려하면 시간 초과가 우려됨.

3. 모든 경우의 수를 탐색하되, 이분 탐색을 사용하여 시간 복잡도를 줄인다.

 

위와 같이 생각했다면,

이분 탐색 함수를 우선 구현하고,

전체 용액에 대해 이분 탐색을 실행하는 알고리즘을 생각할 수 있었을 것이다.

 

세상은 넓고 똑똑쓰들은 많다..

나도 한 자리 주쇼..