[프로그래머스] 완주하지 못한 선수 문제 풀이(해시 Lv.1) - 파이썬 Python

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

문제 접근

우선, 문제를 간단하게 만들어 보면 좋다.
Participant 배열에는 N명의 참가자의 이름이 들어있다. Completion 배열에는 N-1명의 완주자들이 있다.
완주하지 못한 한명을 찾으면 된다.

방법 1 : Sorting 한 뒤에 Loop을 통해 1:1 비교를 하고, 서로 다른 항목이 나온 사람이 완주하지 못한 사람이다.
방법 2 : 해시를 사용하는 방법 (해시 문제이므로 이 방법이 좋지 않을까?)
방법 3 : collections.Counter를 활용한 Solution이 있다.

 

방법 1 - Sort / Loop을 사용한 문제풀이

• 해시문제라서 해시로 풀어야 하지만, 시험에서는 유형을 정해주지 않는다.
• 난이도가 높은 문제를 Sort/Loop으로 풀려고 시도하는 것은 대부분 시간 낭비인 경우가 많지만, 
  이 문제와 같이 간단한 문제는 Loop을 2중/3중으로 만들지 않고 1중 Loop로 만들 방법이 생각난다면 
  도전해볼만 하다.

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

    # 1. 두 list를 sorting한다.
    participant.sort()
    completion.sort()

    # 2. completion list의 len만큼 participant를 찾아서 없는 사람을 찾는다.
    for i in range(len(completion)):
        if(participant[i] != completion[i]):
            return participant[i]

    # 3. 전부 다 돌아도 없을 경우에는 마지막 주자가 완주하지 못한 선수이다.
    return participant[len(participant) - 1]

1. 정렬

• 정렬을 해놓고 동일 index 번호끼리 비교를 해야 한다.

2. 1중 Loop 돌며 다른 참가자 찾기

• Completion 배열을 기준으로 잡고 처음부터 끝까지 돌면서 비교한다.
• 양쪽 배열을 다 정렬했기 때문에, 같은 index의 값이 다르다면, Participant[index]의 값이 정답이 될 것이다.
• 0번 Index부터 돌면서 두 배열의 값이 같은지 비교한다.
• 이때, Completion 배열은 완주한 사람들의 List이니 Completion[Index]는 정답이 될 수 없다.

3. 예외 처리 (Exception)

• 일반적인 케이스 외에도 항상 예상치 못한 경우가 나오기 마련이다.
• 예외처리를 잘 하는 것이 매우 중요하다.
• Sort / Loop 를 이용한 코드는 Completion을 기준으로 돌기 때문에, 완주하지 못한 선수가 Participant 배열의 마지막 Index에 있다면 처리가 되지 못한다. 
• 따라서 그때에는, 마지막에 Participant[-1]를 반환하면 정답을 반환할 수 있게 된다.

 

방법 2 - Hash를 이용한 문제풀이

• Hash 문제이고 Hash개념을 이해하는 것이 중요하니 이번에는 Hash를 이용하여 풀어보자.
• Hash를 사용하더라도 결국 우리가 원하는 것은 Participant 배열에 있고, Completion에 없는 한 명을 찾는 것이다.

def solution(participant, completion):
    hashDict = {}
    sumHash = 0

    # 1. Hash : Participant의 dictionary 만들기
    # 2. Participant의 sum(hash) 구하기
    for part in participant:
        hashDict[hash(part)] = part
        sumHash += hash(part)

    # 3. completion의 sum(hash) 빼기
    for comp in completion:
        sumHash -= hash(comp)

    # 4. 남은 값이 완주하지 못한 선수의 hash 값이 된다.

    return hashDict[sumHash]

# print(solution(["marina", "josipa", "nikola", "vinko", "filipa"] , ["josipa", "filipa", "marina", "nikola"]))

1. Hash Map 만들기

• Hash Map이란 Key-Value의 Pair를 관리하는 클래스이다.
• 이 문제에서 Key는 Hash한 값이고, Value는 각 선수의 이름이다.

2. Hash Map에 Paricipant 추가하기

• 'Hashing을 한다'라고도 표현하는데, Hash Map에 Participant를 전부 추가해보자.
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.

완주하지 못한 선수 - 해시

• Hash Map을 보고 나면 매우 간단하다. 이 문제에서는 각 이름의 Hash 값을 구하고, 이 값들의 합을 구한다.
• sumHash는  35가 된다.

3. sumHash에서 완주한 선수의 Hash값 빼기

• sumHash에서 완주자들을 제외시키면, 한 명만 남게 될 것이고 그 사람이 우리가 찾는 정답일 것이다.
• 위와 동일하게 예제를 통해서 보도록 하겠다.

완주하지 못한 선수 - 해시

4. Value가 0이 아닌 참가자 찾기

• 남아있는 1명이 완주하지 못한 사람이니, sumHash = 5인 Key를 가지고 있는 사람을 찾으면, 완주하지 못한 선수가 나온다.
• 그래서 hashDict[sumHash]라는 코드가 나오게 된다.

 

방법 3 - Counter를 사용한 문제풀이

import collections
def solution(participant, completion):
    # 1. participant의 Counter를 구한다.
    # 2. completion의 Counter를 구한다.
    # 3. 둘의 차를 구하면 정답만 남아있는 Counter를 반환한다.
    answer = collections.Counter(participant) - collections.Counter(completion)

    # 4. counter의  key값을 반환한다.
    return list(answer.keys())[0]

1. Counter이해하기

• Python이 제공하는 collections라는 모듈의 한 class이다.
• list를 가지고 Counter를 생성하면, Counter는 Key가 이름이고, Value가 count인 dictionary를 반환하게 된다.

counter

2. participant / commletion 배열을 Counter로 변환하기

• 위와 동일한 방식으로 completion list도 counter로 만들 수 있다.

python counter

3. participant와 completion 배열 간의 차 구하기

• collections. Counter(participant) - collections.count(completion)
  • Counter class는 상호간의 뺄셈 연산을 지원한다.
  • 즉, 뺄셈 연산 한번으로 participant는 있고, completion에는 없는 사람을 찾을 수 있다.

collections.Counter

4. 마지막 Counter에서 Key값을 읽어오기

• 3단계의 결과는 dictionary로 나오는데, 이중 우리는 Key를 꺼내와야 한다.
  • list(answer.keys())[0]
  • answer로 부터 Keys를 꺼내온다.
  • Keys를 list로 형변환 하고
  • 이 중 0 번째 인덱스의 값을 읽어온다.
• 위 동작을 수행하고 나면 {"A" : 1} 이라는 Dict로부터 ["A"]라는 list를 꺼내오게 되고, 여기서 [0]으로 접근하면 "A"라는 String을 꺼내오게 된다.
• 이를 반환하면 정답이다.

 

---

다음에도 이런 문제를 풀기 위해서는 문제 접근 방식과 Hash 사용 방법을 숙지하고, 비슷한 문제를 보았을 때, "Hash를 쓰면 되겠는걸?"이라는 생각으로 귀결될 수 있도록 연결시키는 것이 코딩테스트의 핵심이라고 생각한다.

만약 이글에 잘못된 부분이 있다면 댓글을 남겨 주시면 개선하도록 하겠습니다.

 

완주하지 못한 선수