백준 20366번 파이썬 문제풀이(같이 눈사람 만들래?) - 투 포인터

 

---

이 문제 정말 어려웠다. 기존 투포인터 응용 문제라 아무리 생각해도 답이 생각 나지 않았다. 그렇게 힌트를 얻어서 생각 한것이 우선 2개의 합을 이중 반복문을 돌아서 각각의 인덱스 와 함께 저장한다. ( a, b , array[a+b]) 와 같은식, 그렇게 이렇게 2개의 합을 찾은 리스트를 우선 정렬한다. 그 후 다시 이중 반복문을 돌면서 앞에서 부터 인덱스 4개가 모두 다른 합 2개를 뽑으면 처음 찾은 그것이 바로 최소 차가 되는 것이다. (왜냐하면 그 이후에 찾은 것은 이미 앞에 뽑은 수 보다 무조건 크기 때문에 차가 커질 수 밖에 없다.) 

 

N = int(input())
array = list(map(int, input().split()))

new_arr = []

for i in range(N):
    for j in range(i + 1, N):
        new_arr.append([i, j, array[i] + array[j]])

new_arr.sort(key=lambda x: x[2])


result = 1 << 100

for i in range(len(new_arr)):
    for j in range(len(new_arr)):
        if (new_arr[i][0] != new_arr[j][0]) and (new_arr[i][0] != new_arr[j][1]) \
                and (new_arr[i][1] != new_arr[j][0]) and (new_arr[i][1] != new_arr[j][1]) and (result > abs(new_arr[i][2] - new_arr[j][2])):
            result = abs(new_arr[i][2] - new_arr[j][2])
            break

print(result)

-> C++은 통과가 되는데 파이썬은 당연히 시간초과가 나는 코드이다.

 

따라서 이는 이중반복문안에 해결할 수 있는 투포인터로 풀어야 하는 걸 구글링을 통해 깨달았다.

이런 투포인터 형식은 처음봤다. 훌륭한 코드인거 같다. 

우선 최소 2칸이상을 확보하여 a x x b 우선 a ,b 기준을 잡아준다. 그 후 계속해서 x 부분을 투포인터 돌리면서 b를 인덱스 맨 끝까지 땡기는 것이다. b가 한칸 땡겨질 때마다 x도 하나씩 늘어난다. 자세한 부분은 코드를 통해 확인하자.

import sys


# 투포인터 실행 함수
def two_pointer():
    global ans

    for i in range(N):
        for j in range(i + 3, N):
            s, e = i + 1, j - 1  # 투포인터를 돌릴 지점을 i 와 j의 사이로 잡아줍니다.
            while s < e:  # s 가 e 보다 작을때만 돈다.
                tmp = (arr[s] + arr[e]) - (arr[i] + arr[j])
                if abs(ans) > abs(tmp):  # 만약 절대값 차가 저장된 값보다 작다면
                    ans = abs(tmp)  # 그 값을 저장
                elif tmp == 0:  # 만약 0이라면 더이상 검사할 필요가 없으므로 
                    ans = 0  # 0을 저장하고
                    return  # 탈출

                if tmp > 0:  # 만약 tmp가 양수라면 더 커지면 안되기 때문에 끝인덱스를 한칸 땡긴다.
                    e -= 1
                else:  # 만약 tmp가 음수라면 더 작아지면 안되기 때문에 시작인덱스를 한칸 뒤로 민다.
                    s += 1


N = int(input())
arr = list(map(int, input().split()))
arr.sort()  # 정렬
ans = sys.maxsize

two_pointer()  # 투포인터 함수 실행
print(ans)