[프로그래머스] 시소 짝꿍 문제. 배열이 길다면 해시를 생각해보자.

서론

프로그래머스 - 시소 짝꿍
https://school.programmers.co.kr/learn/courses/30/lessons/152996

유사한 문제가 자주 나옴에도 불구하고 비슷한 실수를 반복하는 것 같아 기록하고자 글을 작성한다.

해당 문제에서 주어진 제한사항은 배열의 길이가 100,000으로 상당히 탐색에 시간이 많이 소요될 것이다. 이런 경우 완전 탐색으로는 시간 초과가 발생하므로, 이진 탐색, dfs 등 여러 옵션을 생각할 수 있다. 하지만 이렇게 단순 값을 비교하는 문제는 해시부터 시도해보는 것이 좋다. 

문제 풀이

1차 시도 - combinations 사용

결과: 시간 초과

 

from itertools import combinations
def solution(weights):
    answer = 0
    
    for left, right in combinations(weights, 2):
        if left == right:
            answer += 1
        elif left * 2 == right * 3:
            answer += 1
        elif left * 3 == right * 2:
            answer += 1
        elif left * 2 == right * 4:
            answer += 1
        elif left * 4 == right * 2:
            answer += 1
        elif left * 3 == right * 4:
            answer += 1
        elif left * 4 == right * 3:
            answer += 1
            
    return answer

첫 시도는 직관적으로 떠오르는대로 풀어봤다. 하지만, 이렇게 풀 경우 아래와 같이 시간 초과가 뜬다.

모든 element를 검사하는데 상당한 시간이 소요되기 때문에 주어진 문제 조건에서 배열의 길이가 10만 개까지 갈 수 있기 때문에 시간 초과가 발생하는 것이다.

2차 시도 - 해시

결과: 성공


지난 글과 비슷한 케이스인 것 같은데, 이렇게 배열이 주어지고 배열의 길이가 너무 길어서 탐색에 시간이 오래 걸릴 것 같다면, 해시를 써볼 생각을 할 수 있다. 

지난 글의 카카오 보석 쇼핑 문제도 배열의 크기가 100,000까지 주어진다. 이 경우에도 딕셔너리를 사용하여 문제를 풀었다.

해당 문제는 조금 다른 방식으로 딕셔너리를 사용했는데, 바로 딕셔너리에서 값을 빼는 경우가 없다는 것이다.

for 문 하나로 순차탐색으로 모든 경우의 수를 계산하기 위해 딕셔너리를 아래와 같이 누적합을 구하기 위해 사용했다.

 

from collections import defaultdict
def solution(weights):
    answer = 0
    weights.sort()
    dic = defaultdict(int)
    
    for weight in weights:
        two_of_three = weight * 2 / 3
        two_of_four = weight * 2 / 4
        three_of_four = weight * 3 / 4
        
        if weight in dic:
            answer += dic[weight]
        if two_of_three in dic:
            answer += dic[two_of_three]
        if two_of_four in dic:
            answer += dic[two_of_four]
        if three_of_four in dic:
            answer += dic[three_of_four]
        dic[weight] += 1
            
    return answer

정렬을 사용했기 때문에 뒤에 검사하는 숫자는 앞에서 검사하는 숫자보다 크다. 그렇기 때문에 현재 검사하는 숫자보다 작은 숫자들과의 매칭만 알아보면 된다. 그렇기 때문에 2/3, 2/4, 3/4를 곱한 숫자가 딕셔너리에 존재하는지만 검사하면 된다. 그리고 그 숫자가 존재할 경우 현재 딕셔너리에 있는 모든 값을 가져와 answer에 누적시키면 된다. 그 후에 해당 딕셔너리값을 1 상승시킴 (방금 검사에 사용한 숫자도 개수에 포함되어 갱신되어야 하기 때문)

결론

배열의 길이가 길어서 탐색에 시간이 오래 걸릴 것 같다면, 해시부터 생각해보자.