[프로그래머스 해시]완주하지 못한 선수 - Python3

문제

마라톤에 참가한 선수들 중, 완주하지 못한 선수를 리턴하는 알고리즘을 만들어라.

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

코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스

입력

마라톤에 참가한 명단인 배열 participants

완주한 선수 명단인 배열 completion

• 동명이인이 있을 수 있다.
• 완주하지 못한 선수는 1명이다.
• participants의 길이는 1 ~ 100000 사이이다.
• completion의 길이는 1 ~ len(participants) - 1이다.

출력

완주하지 못한 선수의 이름

 

알고리즘

def solution(participants, completion):
    # 해쉬 테이블을 이용하기 위해 딕셔너리 선언
    hash_table = dict()

    # participants 배열을 순회하면서, 각 원소를 hash_table의 key로 선언한다.
    # 한 이름이 나올 때마다, 그 이름에 해당하는 value를 1 증가시킨다.
    for i in range(len(participants)):
        # key가 이미 존재하고, 그 key에 해당하는 값을 1 증가시키는 try문. 동명이인인 경우를 처리하기 위함이다.
        try:
            hash_table[participants[i]] += 1

        # 해당하는 key가 없을 경우, 새로 만들어 주기 위한 except문
        except:
            hash_table[participants[i]] = 1

    # completion 배열을 순회하면서, 각 원소를 key로써 hash_table에 접근한다. 
    # 그리고 key에 해당하는 value의 값을 1씩 감소시킨다.
    for i in range(len(completion)):
        hash_table[completion[i]] -= 1

    # hash_table의 key들을 순회하면서, value가 0이 아닌 key를 리턴한다. 
    # 즉, 참가자 명단에는 이름이 나왔지만 완주하지는 못한 선수의 이름을 리턴한다.
    for i in hash_table.keys():
        if hash_table[i] != 0:
            return i


participants = ["mislav", "stanko", "mislav", "ana"]
completion = ["stanko", "ana", "mislav"]
print(solution(participants, completion))

 

설명

1. 해쉬 테이블을 선언한다.
2. participants 배열을 순회하면서, 각 원소들을 key로, 한 이름이 몇 번이나 나왔는지를 value로 만들어서 hash_table에 입력한다. 즉, 이름이 key, 출현 빈도가 value
3. completion 배열을 순회하면서, 한 이름이 나올 때마다 해당 이름을 key로 하는 value를 1씩 감소시킨다
4. hash_table의 key들을 순회하면서, value가 0이 아닌 key를 리턴한다.

 

결과

원하는 값을 출력한다.

후기

Level 1인 문제이고, 저번에 해결했던 문제였지만 Hash 방식으로 문제를 해결해보기 위해 다시 한 번 풀어 보았다. 

원래는 두 개의 배열을 sort()함수를 이용해서 정렬하고, 인덱스 i를 통해서 두 배열의 원소가 달라지는 순간의 원소를 리턴하는 방법을 사용했었다. 그런데 이 방법은 배열을 정렬해야 한다는 점에서, 배열의 크기가 커질 경우 효율성 테스트를 통과할 수 있을 지 의문이 들었다. 따라서 새로운 방법인 hash방법을 시도했다. 

def solution(participant, completion):
    answer = ''

    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] == completion[i]:
            pass
        else:
            answer = participant[i]
            break;
    return answer

<원래 썼던 방법>

이전에 썼던 알고리즘과 이번에 새로 만든 알고리즘을 비교해보니, 수행 속도에서 차이가 나는 모습을 볼 수 있다.

시간 비교

입력 데이터의 크기가 작은 경우는 별로 차이가 없었지만, 데이터의 크기가 커질수록 걸리는 시간이 길어짐을 알 수 있었다. 

코딩테스트에서는 문제는 단순하더라도, 입력 데이터의 크기가 너무 커서 배열을 사용하면 안되는 경우가 많았다. 이 점에 유의해서 좀 더 효율적인 자료구조 선택으로 알고리즘의 시간 복잡도를 가능한 한 줄여야 한다는 점을 다시 한 번 배웠다.