[Programmers] 21. 자료구조: 해시 (Hash): 알고리즘 문제풀이(2): 프로그래머스 완주하지 못한 선수

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

---

프로그래머스 완주하지 못한 선수 풀이

• 알고리즘 문제를 풀 때는 주어진 조건을 잘 봐야합니다.
• 제한 사항이 중요한 의미를 지닐 때가 대부분입니다.
• 문제 완주하지 못한 선수의 최대 입력 $N$은 10만이므로 $O(N)$이나 $O(NlogN)$ 정도의 시간복잡도를 가진 방식으로 풀어야합니다.
• 동명이인의 조건 또한 잘 처리해야겠습니다.

자료구조의 선택

• 이름대신 번호가 주어졌다면?
  • 배열을 이용
• 문자열로 접근할 수 있는 좋은 자료구조는 해시(Hash)입니다.

해시 (Hash)

• 해시 (해시 테이블: hash table)
• key와 value를 이용하여 배열처럼 사용이 가능합니다.
• python에서는 Dictionary 자료형({})이 이에 해당합니다.
• 해쉬 함수를 이용하여 O(1)에 접근이 가능하므로 검색이 빈번할 때 사용하기 좋습니다.

해시를 이용한 문제풀이의 복잡도

def solution(participant, completion):
    dic = {}
    for key in participant:
        dic[key] = dic.get(key, 0) + 1
    for k in completion:
        dic[k] -= 1
    answer = [i for i in dic if dic[i] > 0]
    return answer[0]

• 해시 dic을 만들 때, List participant를 모두 탐색하기 때문에 $O(N)$의 시간이 걸립니다.
• dic[k]를 감소시킬 때, List completion을 모두 탐색하기 때문에 $O(N)$의 시간이 걸립니다.
• answer = [i for i in dic if dic[i] > 0]에서 해시 dic을 모두 탐색하므로 $O(N)$의 시간이 걸립니다.

배열의 정렬을 이용한 문제풀이의 복잡도

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

• for 반복문을 돌 때 $O(N)$의 시간이 걸리지만,
• 그 전에 List participant와 completion을 정렬할 때 $O(NlogN)$의 시간이 들었기 때문에
  전체적인 시간복잡도 또한 $O(NlogN)$에 지배된다고 할 수 있습니다.

---

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.