[백준 20366] 같이 눈사람 만들래? (Python)

www.acmicpc.net/problem/20366

20366번: 같이 눈사람 만들래?

 

문제풀이

N, arr : 입력값

left, right : 투 포인터

tmp : 두 눈사람의 키 차이

 

세 용액 문제에서 조금 더 나아가서 네 용액(?) 문제인 것 같다. 미리 두개의 원소를 지정하고, 해당 두 원소 사이에서 투 포인터(Two-Pointer)를 통해 두 눈사람의 키 차이의 최소값을 구하는 것을 반복하면서 해결할 수 있다.

 

1. 배열 arr를 정렬해준다. (원본 배열의 순서를 변경해도 무방하므로)

 

2. 두 원소를 선정해서 투 포인터를 진행한다.

- 특정 두 원소를 선정할 떄, i번째 원소를 선택할 경우 최소 i+3 번째 이상의 원소를 선택해야 한다. (그래야 두 원소 사이에 최소 2개의 원소가 존재한다.)

- 투 포인터를 통해 두 눈사람의 키 차이의 최소값을 구한다.

 

코드 주석으로 헷갈릴만한 부분 설명되어 있다.

 

코드

import sys

if __name__ == '__main__':
    N = int(input())
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort()
    ans = sys.maxsize
    for i in range(N):
        for j in range(i + 3, N):
            left, right = i + 1, j - 1
            while left < right:
                tmp = (arr[i] + arr[j]) - (arr[left] + arr[right])
                if abs(ans) > abs(tmp):
                    ans = abs(tmp)
                # 정렬이 되어 있기 때문에, tmp 가 0보다 작은 경우는(arr[left] + arr[right] > arr[i] + arr[j])
                # tmp 를 늘릴 필요가 있으므로 right 를 감소
                if tmp < 0: right -= 1
                # 정렬이 되어 있기 때문에, tmp 가 0보다 큰 경우는(arr[left] + arr[right] < arr[i] + arr[j])
                # tmp 를 줄일 필요가 있으므로 left 를 증가
                else: left += 1
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!