프로그래머스 | 해시 - 폰켓몬, 완주하지 못한 선수, 전화번호 목록

해시관련 문제풀이 모음이다. 난이도가 leve 1, 2로 쉬운 편이어서 포스팅을 할지 고민하였으나, 여러 문제를 같이 리뷰하면서 해시 알고리즘에 대한 공통적인 인사이트를 얻을 수 있을 것 같아 정리해보고자 한다.

🔅 폰켓몬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

n/2개의 폰켓몬을 선택할 때, 선택할 수 있는 폰켓몬 종류의 최대를 구하는 문제다.

def solution(nums):
    c = []
    
    for n in nums:
        if n not in c:
            c.append(n)
            
    answer = len(c) if len(c) < len(nums)/2 else len(nums)/2
    
    return answer

 

상단과 같이 매우 간단하게 풀었다.

그런데 너무 hash스럽지 않는 코드인가 .. 싶기도 하고 좀 더 효율적으로 풀 수 있는 방법이 있을 것 같아 다시 시도해보았다.

def solution(nums):
    
    s = set(nums)
    n = len(nums)//2
    
    answer = min(len(s), n)
    
    return answer

 

첫번째 코드에서 in 구문을 써서 c배열에 카테고리를 입력한다는 것은, 결국 중복을 제거한다는 것이다. 만약 해당 카테고리의 세부내용까지 알아야 하는 상황이라면 dictionary를 사용해야겠지만, 현재는 카테고리의 수만 알면 되기 때문에 set을 사용해서 간단하게 표현할 수 있다.

 

그리고 if문을 이용해서 answer의 값을 지정해주었던 것을 min을 이용해서 보다 단순화했다.

 

여전히 hash스럽지 않기는 하지만 ,, 그렇다고 dictionary를 쓰기에는 너무 비효율적이기 때문에 이게 가장 괜찮은 풀이인 것 같다.

 

🔅 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

 

 

위와 같이 마라톤에 참여한 사람 중 완주한 사람을 제외하고 완주하지 못한 사람을 출력하는 문제다.

이 문제의 point는 동명이인이 존재할 수 있다는 것이다. 해당 부분을 주의해서 처리해야한다.

def solution(participant, completion):
    # point -> 동명이인 처리 !!
    
    d = {}
    
    for p in participant:
        if d.get(p) is None:
            d[p] = 1
        else:
            d[p] += 1
    
    for c in completion:
        d[c] -= 1

    
    for key, item in d.items():
        if item != 0:
            answer = key
            break
    
    return answer

 

위와 같이 풀 수 있다. dictionary의 value로 해당 이름의 사람을 카운트한 뒤, completion 배열을 순회하면서 -1을 해주면 된다. 여기에서 value가 0이 된다면 마라톤을 모두 완주한 사람이라고 볼 수 있다.

🔅 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

상단과 같이 접두어를 찾는 문제다. 문제를 보자마자 사전식으로 배열을 하는 방법이 떠올랐다. 전화번호를 오름차순으로 정렬할 경우 가장 가까운 관계(비슷한 상태)에 인접한 문자들이 있게 되며, 따라서 인접한 것들끼리만 조사를 함으로써 접두어를 찾을 수 있다.

def solution(phone_book):
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    
    return True

 

위와 같이 배열을 정렬한 뒤, for문으로 순회하면서 접두어 관계가 있는지를 찾는다.

 

이것 또한 hash를 사용해서 풀었다고 할 수는 없을 것 같아, hash 알고리즘을 활용해서 다시 문제를 풀어보았다.

 

    for number in phone_book:
        phone_dict[number] = True
    
    # 하나씩 digit 단위로 보면서 key가 존재하는지 보기
    for number in phone_book:
        temp = ""
        for digit in number[:-1]:  # 마지막 글자 전까지만 확인
            temp += digit
            if temp in phone_dict:
                return False

 

 

위와 같이 문자를 알파벳 하나씩 조사하면서, dictionary안에 key가 존재하는지 확인한다.

 

두가지 풀이법의 시간복잡도를 비교하면 다음과 같다.

 

1번 풀이 : O(nlogn) 

2번 풀이 : O(n*m)

(n은 phone_book의 길이, m은 문자열의 길이)

 

해당 문제의 경우, n의 최댓값은 1,000,000이고, m의 최댓값은 20이다. m의 최댓값이 크지 않기 때문에 1번 풀이와 2번 풀이의 시간복잡도는 크게 차이가 나지 않는다. 그러나 만약 문자열의 길이가 길다고 하면, 1번 풀이를 사용하는 것이 시간복잡도면에 있어 보다 효율적일 것이다.

🔅 해시를 이용한 문제풀이 정리

사실, 해시 카테고리의 문제임에도 해시 구조 대신 다른 자료구조 및 알고리즘을 사용해서 푼 경우가 더 많다. 그럼에도 해시 구조를 활용한 접근이 도움이 되는 경우가 많아, 문제별로 해시 알고리즘의 장점을 살펴보았다.

해시 구조의 특징

1. dictionary와 set은 내부적으로 해시 구조를 사용하며, **키를 통한 접근 시간 복잡도가 O(1)**이라는 장점이 있다.
2. dictionary의 키는 항상 고유하며, 중복을 자동으로 제거하는 set과 마찬가지로 유일한 값을 가진다.

 

이런 특성 덕분에 해시 알고리즘은 key-value 형식으로 데이터를 저장하고 조회할 때 매우 유용하다. 예를 들어, 특정 카테고리 안에 여러 항목이 존재할 때, 카테고리별 개수만 카운팅하고 세부 내용을 몰라도 되는 문제에서 강력한 성능을 발휘한다. 키를 통한 조회가 O(1) 복잡도로 매우 효율적이며, 특히 긴 문자열 키를 다룰 때 성능 저하가 거의 없는 점에서 해시 알고리즘은 매우 효과적이다.

 

해시 알고리즘의 실제 활용은 다양한 상황에서 볼 수 있는데, 예를 들어 텍스트 기반 데이터에서 특정 문자열의 출현 빈도를 빠르게 파악하거나, 중복을 제거하여 고유한 데이터만 남기는 경우 등이 있다.

🔅 기타

- d.get(index) vs d[index]

d.get(index)의 경우 key가 존재하지 않을 때 에러가아닌 None을 출력하기 때문에, 키가 있을지 없을지 확실하지 않은 상황에서는 get을 사용하는 것이 훨씬 안전하다.