[Python] BOJ 2470 - 두 용액

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

2470번: 두 용액

# 투 포인터 문제중에는 대표적인 문제로 잘 알려져 있는 문제이다.

# 이분탐색을 사용해서 풀 수도 있다는데..(그건 잘 모르겠고)

 

1. nums에 용액들의 특성값을 입력받고 오름차순 정렬해준다.

   두 용액의 최대 차이는 10억 - (-10억) = 20억이므로, tmp를 20억+1로 설정해준다.

 

2. 우선 nums배열을 반복문으로 돌며 용액이 모두 양수이면 가장 작은 값과 두번째로 작은 값을 출력한다.

    모두 음수이면 두번째로 큰 값과 가장 큰 값을 출력한다.

 

3. 왼쪽 포인터 i = 0, 오른쪽 포인터 j = N-1로 설정하고 반복문을 진행시킨다.

   3-1. 만약 nums[i] + nums[j]가 0이라면 그 즉시 두 용액을 출력하고 종료한다.

         (특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는

           그 중 아무것이나 하나를 출력하면 되기 때문)

   

   3-2. 만약 두 용액의 차이가 tmp(최소차이)보다 작다면 tmp를 갱신해주고 ans에 두 용액을 저장해준다.

   

   3-3. 만약 두 용액의 합이 0보다 크다면 왼쪽 포인터를 1 증가시키고

            0보다 작다면 오른쪽 포인터를 1 감소시킨다.

 

4. i가 j와 같아지거나 j보다 커지면 반복문을 중단하고, 마지막까지 sys.exit(0)에 걸리지 않으면

    ans에 저장된 값을 출력해준다.

 

import sys
input = sys.stdin.readline
N = int(input())
nums = list(map(int,input().split()))
nums.sort()
tmp = 2000000001
pos, neg = 0, 0
for i in nums:
    if i > 0:
        pos += 1
    elif i < 0:
        neg += 1
if pos == N:
    print(nums[0], nums[1])
    sys.exit(0)
elif neg == N:
    print(nums[-2], nums[-1])
    sys.exit(0)

i, j = 0, N-1
while True:
    if i >= j:
        break

    if nums[i] + nums[j] == 0:
        print(nums[i], nums[j])
        sys.exit(0)

    if abs(nums[i] + nums[j]) < tmp:
        tmp = abs(nums[i] + nums[j])
        ans = [nums[i], nums[j]]
    
    if nums[i] + nums[j] > 0:
        j -= 1
    elif nums[i] + nums[j] < 0:
        i += 1
print(*ans)

(solved.ac 티어: 골드 5)

 

============================================================================

# 다른 사람들의 코드를 보니 내 코드에 너무 불필요한 부분이 많아서 

   불필요한 부분을 제거하고 깔끔하게 남겨보았다.

 

import sys
N = int(input())
nums = list(map(int,input().split()))
nums.sort()
tmp = 2000000001

i, j = 0, N-1
while i < j:
    if nums[i] + nums[j] == 0:
        print(nums[i], nums[j])
        sys.exit(0)

    if abs(nums[i] + nums[j]) < tmp:
        tmp = abs(nums[i] + nums[j])
        ans = [nums[i], nums[j]]
    
    if nums[i] + nums[j] > 0:
        j -= 1
    elif nums[i] + nums[j] < 0:
        i += 1

print(*ans)

# 시간은 30ms정도 차이나서 별 차이가 없어보인다.