[백준] 같이 눈사람 만들래?

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

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

4개의 수중 2개씩 수를 더한 다음 합쳐진 2개의 수의 차이가 적게 되도록 해야합니다. 차이가 작아지려면 2개의 수를 합칠 때에 반드시 (가장 큰 수 + 가장 작은 수), (2번째로 큰 수 + 3번재로 큰 수)가 되어야한다는 점을 활용하여 풀이하였습니다.

눈덩이를 오름차순으로 정렬한 다음 가장 작은 수와 가장 큰 수를 각각 i, j가 가르키도록 합니다. 그리고 해당 범위 안을 투포인터로 탐색하면서 차이가 가장 작아지는 경우를 찾는 방식으로 풀이하였습니다. 시간 복잡도는 대략 O(600C2 * 600)으로 간신히 통과할 수 있었습니다.

 

import sys

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))

nums.sort()

ans = sys.maxsize

for i in range(n - 3):
    for j in range(i + 3, n):
        left, right = i + 1, j - 1
        # 현재 두 수의 합
        cur = nums[i] + nums[j]

        while left < right:
            sum = nums[left] + nums[right]
            ans = min(abs(sum - cur), ans)
            if sum > cur:
                right -= 1
            elif sum < cur:
                left += 1
            else:
                print(0)
                sys.exit(0)
print(ans)

 

처참한 실행시간...

 

빠른 수행시간을 보인 다른 분들의 코드를 보고 개선된 풀이입니다. 먼저 모든 2개 눈덩이의 조합을 구해줍니다. 그 다음 눈덩이의 합을 기준으로 오름차순으로 정렬해줍니다. 오름차순으로 정렬되면 현재 눈사람의 다음에 위치하는 눈사람은 현재 눈사람보다 크면서 가장 적은 차이를 가지게 되는 눈사람이 되게 됩니다. 이를 활용하여 현재와 오른쪽에 있는 눈사람 조합에서 서로 겹치는 눈덩이가 있는지 체크하고 답을 갱신해주면 됩니다. 이렇게 되면 O(600C2 + 600C2)가 되므로 훨씬 나은 실행시간이 나오게 됩니다.

 

import sys

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))

# (두 눈덩이의 합, 선택된 눈덩이 i, j)
snowmans = [
    (nums[i] + nums[j] , i,  j)
    for i in range(n)
    for j in range(i + 1, n)
    if i != j
]

# 두 눈덩이의 합을 오름차순으로 정렬
snowmans.sort()

left, right = 0, 1
ans = sys.maxsize

while right < len(snowmans):
    sm1, i1, j1 = snowmans[left]
    sm2, i2, j2 = snowmans[right]

    left += 1
    right += 1

    # 눈덩이의 조합이 겹치는 경우가 있으면 넘어간다.
    if i1 == i2 or i1 == j2:
        continue
    if j1 == i2 or j1 == j2:
        continue

    ans = min(ans, sm2 - sm1)

print(ans)

 

편안~