코드

# 두 용액의 합이 0에 가장 가까운 값을 만들자
n = int(input())

# 전체 용액 리스트 입력
arr = list(map(int, input().split()))

# 투 포인터 정렬 필수
arr.sort()

# 시작과 끝 인덱스 생성
start = 0
end = n-1

# 두 값의 합을 저장할 변수
# 가장 합이 큰 경우 == 맨 처음 + 맨 끝
tot = arr[start] + arr[end]

# 최종 출력에 사용할 두 인덱스를 생성
idx1 = start
idx2 = end

while start < end:
    
    # tot와 값을 비교하기 위한 임시 변수 생성
    tmp = arr[start] + arr[end]
    
    # tot, tmp 값의 크기 비교를 위해 절댓값 사용
    
    # tmp가 더 작으면 tmp를 tot로 변경
    # 인덱스 2개도 현재의 인덱스로 변경
    if abs(tmp) < abs(tot):
        tot = tmp
        idx1 = start
        idx2 = end
    
        # 0에 가까운 값을 찾는데 0이 나오면 그냥 바로 출력해줌
        # 어차피 아무거나 하나 출력하면 되니까
        # 이 이상 반복을 수행할 필요가 없음
        if tot == 0:
            break
    
    # tmp의 값이 0보다 작다
    # => start의 값 1 증가
    # => arr[start]보다 arr[start+1]이 값이 더 큼
    # => tmp의 값 역시 커짐
    if tmp < 0:
        start += 1
        
    # tmp의 값이 0보다 크거나 같다
    # 작을 때와 동일한 로직
    else:
        end -= 1
        
print(arr[idx1], arr[idx2])

문제 해설

투 포인터 알고리즘의 활용 문제이다.

주어지는 용액들 중 2개를 골라 농도 합의 결과가 0에 가장 가까운 두 용액을 고르는 문제이다. 사실 처음 문제 자체를 잘못 파악하여 용액의 단순 합이 아니라 알칼리성인지 산성인지에 따라 로직을 나눠서 처리해야 하는 것으로 오해하여 문제를 상당히 복잡하게 풀려고 시도했었다. 계속 오답 처리가 되어서 결국 문제를 다시 한 번 꼼꼼히 읽어보니 그냥 모든 용액 중 성질을 구분하지 않고, 두 합의 값이 0에 가깝기만 하면 되는 것임을 파악한 후엔 비교적 쉽게 해결할 수 있었다.

문제의 설명은 대부분 주석에 있으며, 알고리즘 자체도 크게 복잡하지 않아 기존의 투 포인터 문제의 설명으로 대신하곘습니다.

기본 투 포인터 문제 - 두 수의 합

댓글남기기

참고