(프로그래머스 해시 문제 풀이) 완주하지 못한 선수, 전화번호 목록

해시(Key-value쌍으로 데이터를 저장하는 자료구조)

완주하지 못한 선수

문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예
participant                                                    completion                                          return
["leo", "kiki", "eden"]                                      ["eden", "kiki"]                                         "leo"
["marina", "josipa", "nikola", "vinko", "filipa"]        ["josipa", "filipa", "marina", "nikola"]             "vinko"
["mislav", "stanko", "mislav", "ana"]                    ["stanko", "ana", "mislav"]                         "mislav"

입출력 예 설명
예제 #1"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #2"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #3"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

def solution(participant, completion):
    par_dic = dict(zip([i for i in range(len(participant))], sorted(participant)))
    com_dic = dict(zip([i for i in range(len(completion))], sorted(completion)))
    for i in range(len(completion)):
        if par_dic[i] != com_dic[i]:
            return par_dic[i]

    return par_dic[i+1]

해당 문제는 얼핏 보기에 굉장히 간단한 문제지만, 효율성 테스트에서 많은 사람들이 "실패" 라는 문구를 마주할 것이다.(저도 그랬습 읍..ㅎ) 처음에 간단하게 생각하여 작성한 코드를 아래 첨부한다.

# 효율성 테스트 통과 X
def solution(participant, completion):
    for player in completion:
        if player in participant:
            participant.remove(player)
            
    return participant[0]

for 문을 한 번만 썼음에도 리스트의 remove() 함수로 인해 시간 복잡도가 $O(N^2)$가 된다. 

아래는 참고 코드인데, 실제 hash() 함수를 사용하여 구현한 것이라 공부에 도움이 될 것 같아 가져왔다. 좋아요를 가장 많이 받은 코드는 collections 모듈을 불러와 Counter() 함수를 사용하는 것인데, hash 개념을 익히기에 좋은 2번째 코드를 첨부한다.

# 모범 참고 코드
def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += hash(part)
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

해쉬는 키 값이 같으면 동일한 데이터로 판단한다는 특징을 잘 살렸다. 단, 여러 키에 해당하는 주소가 같을 경우 충돌이 난다는 위험성은 존재한다. 해쉬에 대한 설명은 해당 블로그를 참고하면 좋을 것 같다. 

---

전화번호 목록

문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제
phone_book                                 return
["119", "97674223", "1195524421"]     false
["123","456","789"]                          true
["12","123","1235","567","88"]            false

입출력 예 설명
입출력 예 #1 앞에서 설명한 예와 같습니다.
입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

def solution(phone_book):
    phone_book.sort()
    for idx in range(len(phone_book) - 1):
        # 앞뒤로만 비교해서 앞에 있는 숫자 길이만큼 잘라 확인하기
        if phone_book[idx] == phone_book[idx+1][:len(phone_book[idx])]: 
            return False
    return True

해당 문제는 위 코드처럼 해시를 풀지 않아도 해결할 수 있다. 그래서 찜찜하지만 해시를 사용할 경우보다 효율성 테스트에서 높은 성능을 보여주어 뭐가 맞는지 모르겠다. 리스트를 정렬하면 앞뒤 숫자만 비교하면 되고, 이때 뒤의 숫자를 앞의 숫자 길이만큼 인덱싱했을 때 같으면 접두사다. 

아래는 해시를 사용한 것으로, 효율성 테스트도 통과를 한다. 하지만 위의 방법과 비교했을 때는 시간이 더 소요된다. 

# 모범 참고 코드
def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1 # 각 전화번호별 value 값은 1로(아무 값이나 상관없음)
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number: # hash_map에 포함되고, 전화번호 자체가 아닌, 즉 접두어인 경우
                answer = False
    return answer