[백준/투 포인터] - 같이 눈사람 만들래?(ref)

문제 링크

✅ PyPy3로 제출해야 함

코드

# 서로 다른 눈덩이를 4개 선택해야 한다.
# 투 포인터를 2개 사용해야 하는데 어떻게?
n = int(input())
_list = sorted(list(map(int, input().split())))

l, r = 0, n - 1
_min = int(1e9)

# l1, r1: 엘자의 포인터
for l1 in range(n):
    for r1 in range(l1 + 3, n):
        l2, r2 = l1 + 1, r1 - 1 # l2, r2: 안나의 포인터
        
        while l2 < r2:
            diff = (_list[l1] + _list[r1]) - (_list[l2] + _list[r2])
            if abs(diff) < _min: # 키 차이가 더 작다면 갱신
                _min = abs(diff)
            
            if diff < 0: # l2 + r2가 더 크다면 r2를 줄여야 한다.
                r2 -= 1
            else: # l2 + r2가 더 작다면 l2를 늘려야 한다.
                l2 += 1
print(_min)

풀이

문제의 목표

• 두 눈사람의 키 차이 중 최솟값 구하기

일단 서로 다른 눈덩이 4개를 골라야 하고 키 차이는 최소여야 하므로 눈덩이가 저장된 리스트를 오름차순 정렬했다.

그리고 엘자와 안나 각각의 투 포인터를 어떻게 설정할지 고민했다.
이에 대한 답이 내려지지 않아, 다른 사람의 풀이를 참고했다.

로직은 다음과 같다.

1. 엘자의 포인터를 설정한다.(단, l과 r의 사이에 눈덩이가 2개 이상이 되도록)
2. 안나의 포인터는 l과 r 사이에 위치시킨다.(→ l+1, r-1로 설정한다.)
3. 안나의 포인터를 조절하면서 두 눈사람의 키 차이를 확인하고 조건에 맞으면 갱신한다.(이는 안나의 오른쪽 포인터가 왼쪽 포인터보다 클 때 까지 계속한다.)
4. 엘자의 오른쪽 포인터를 1 늘려서 다시 2~3을 반복한다.