[Python] BOJ 20366 - 같이 눈사람 만들래?

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

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

# 랜덤으로 4개를 뽑아서 비교하면 nC4이므로 당연히 시간초과이다.

   따라서 '세 용액'문제와 비슷하게, 미리 기준점을 하나 설정하고 나머지 2개의 원소를

   '투 포인터' 알고리즘을 사용해서 비교하며 풀었다.

 

1. 우선 i와 j를 설정한다. (i 와 j의 차이는 3이상) -> 그래야 최소 i와 j사이에 원소 2개이상 존재

 

2. 기준점인 눈사람 한개를 fix로 설정 (snow[i] + snow[j])

 

3. i와 j사이에서 투 포인터를 사용해 두번째 눈사람의 키를 구해주고 첫번째 눈사람(fix)와의 차이를 비교한다.

     3-1. 두 눈사람 키의 차이가 diff보다 작다면 diff값을 갱신

 

     3-2. 두 번째 눈사람의 키가 첫번째 눈사람보다 작다면 left를 1증가시켜서

            두 번째 눈사람의 키를 증가시킨다. (첫번째 눈사람은 고정이므로 크기를 변경하면 안된다.)

 

     3-3. 두 번째 눈사람의 키가 첫번째 눈사람보다 크다면 right를 1 감소시켜서

             두 번째 눈사람의 키를 감소시킨다.

 

     3-4. 두 눈사람의 키가 같으면 답이 0이되므로 바로 출력하고 프로그램 종료

 

4. 최종적으로 diff에 있는 값 출력

 

import sys
input = sys.stdin.readline
N = int(input())
snow = list(map(int,input().split()))
snow.sort()
diff = 4000000001
for i in range(N-3):
    for j in range(i+3, N):
        fix = snow[i] + snow[j]
        left, right = i+1, j-1

        while left < right:
            s = snow[left] + snow[right]
            if abs(s - fix) < diff:
                diff = abs(s - fix)
            
            if s < fix:
                left += 1
            elif s > fix:
                right -= 1
            else:
                print(0)
                sys.exit(0)

print(diff)

(solved.ac 티어: 골드 3)