BOJ 20366) 같이 눈사람 만들래? (+ hashing의 강력함)

중간고사와 정보처리기사 실기로 인해 마지막으로 고민하던 문제에서 나아가지 못했다. 약 3주 정도 공백이후 다시 풀어보려 시도했고 해결에 성공했다.

문제)

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

입력)

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

출력)

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라

---

풀이...

처음엔 간단한 투 포인터 문제인줄 알고 만만하게 봤지만 쉽게 해결이 되지 않아 난감했다.

딱 보기에는 간단한 Two sum문제 였는데, 비교군이 되는 두 눈사람 중 하나를 기준으로 삼아서 풀어나가려 했으나, 인덱스를 어떻게 움직여야할 지 난감했다. 아무래도 target이 없으니 더 커지는 방향으로 인덱스를 조정할지, 작아지는 방향으로 인덱스를 조정할지, 도대체 무엇과 비교하여 커져야하는지 작아져야하는지 감이 오지 않아서 가능한 다양한 방법을 시도했었다.

문제 입력 조건을 보면 6 * 100이 최대 길이이다. 보통 10^8보다 큰 시간복잡도는 시간초과문제를 일으킨다. 그래서 안전하게 O(n^2) 으로 접근하려 한게 화근이 되었다.

입력의 길이가 작다는 것과 비교 기준이 될 한 눈사람의 크기를 조절하는 조건이 불분명하다는 점에서 완전탐색을 이용하기로 하였다.

우선 다음과 같은 가정이 필요했다. 눈덩이 배열내의 원소 A B C D가 있을 때,
A < B < C < E < D 이고, B = A + a, C = E - b, D = E + c라고 하자.

두 눈사람의 차이를 계산하고자 할 때, 어떤 식으로 탐색범위를 한정할 수 있을까?

눈덩이 A와 E는 하나의 눈사람이 될 수 있다. 그를 제외한 눈덩이들도 눈사람을 만들 수 있으니 직관적으로 좋아보이는 조합을 이용해보자.

(A+E) - (B + C) = b - a
(D + B) - (A + E) = c + a

이므로 A와 E로 눈사람을 만들때는 A, E 사이에 있는 두 개의 눈덩이를 사용해야 가장 차이가 적은 눈사람을 만들 수 있다.

이때 A와 E를 정하는 것을 완전탐색으로 만들면 대략 n^2번 반복될 것이다.

A+E와 차이가 가장 작은 눈사람 크기를 A에서 E 사이 범위내를 탐색해 찾는 시간복잡도는 O(n)이다.(Two sum 알고리즘)

그러므로 전체 시간복잡도는 O(n^3)이 될 것이다.

1.86e8은 10^8보다 크다. 따라서 시간초과 문제가 발생할 가능성이 농후하다.

이때 해시를 적용해서 불필요한 탐색을 생략하는 방법을 이용한다.

눈덩이 A와 E의 합을 Hash set에 저장해두고, 이 크기의 눈덩이가 재등장하면 탐색하지 않는다.

예를들어 어떤 눈덩이 배열의 부분배열이 2 3 4 7 8 9라고 하자.
A가 2, E가 9일때 A + E는 11이다. 내 가정이 유효하기 위해서는 저 부분배열 밖 인덱스에서 (적어도 두 눈덩이 중 큰 것은 2보다 작거나 작은 것이 9보다 커야한다. -> 즉, 교집합이 발생하지 않는 두 눈덩이를 선택한다는 의미이다.) 두 합이 11인 눈덩이 조합이 발생해선 안된다.

왜냐하면 우리가 위의 저 부분배열이나 혹은 합이 11인 다른 부분배열을 한 번 탐색했다면 Hash set엔 11이 저장되어 있을 것이고, 아직 탐색하지 않은 다른 부분배열의 차례가 되었을 때 저장된 11로 인하여 탐색하지 않게되어 최소 크기 차이를 놓칠 수 있기 때문이다.

다행히도 저 부분배열 밖의 서로 교집합이 없는 두 눈덩이로는 동일한 크기의 눈사람을 만들 수 없음은 자명하다고 볼 수 있다. 이를 이용해 연산 횟수를 줄일 수 있다.

추가적으로 차이가 0인 경우 더이상 작아질 수 없으므로 바로 함수를 종료해 단축시킬 수도 있다.

다음은 프로그램 코드이다.

import sys

def searchTarget(nums, target) :
    left = 0
    right = len(nums) - 1
    min_diff = sys.maxsize
    while left < right:
        min_diff = min(min_diff, abs(target - (nums[left] + nums[right])))
        if nums[left] + nums[right] < target :
            left += 1
        else :
            right -= 1
    return min_diff

def solve() :
    N = int(input())
    snow_balls = list(map(int, input().split()))
    snow_balls.sort()
    height_set = set() # hash set
    smallest_difference = sys.maxsize
    
    for right in range(N-1, 2, -1) :
        for left in range(0, right - 2) :
            h = snow_balls[left] + snow_balls[right]
            if h not in height_set :
                height_set.add(h)
                min_diff = searchTarget(snow_balls[left+1:right], h)
                smallest_difference = min(min_diff, smallest_difference)
                if not smallest_difference :
                    print(0)
                    return
    print(smallest_difference)
    return

'''
8
1 3 4 6 1325 8746 12566 8756254 
0
'''
solve()