알고리즘 문제- 완주하지 못한 자

  • 이번 포스트에서는 오늘 해결했던 알고리즘 문제에 대한 다양한 해답에 대해 소개해볼 것이다.

문제 : 완주하지 못한 선수

문제 설명

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

제한사항

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

문제 해답

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# 방법 1) dictionary 사용
from functools import reduce
def solution(participant, completion):
    # 참가자, 완주자들 각각 이름을 key로, 그 이름을 가진 사람들의 숫자를 value로 설정하여 dictionary 타입의 변수를 생성한다.
    participant_dic = reduce(lambda dic, ch: dic.update({ch: dic.get(ch, 0)+1}) or dic, participant, {})
    completion_dic = reduce(lambda dic, ch: dic.update({ch:dic.get(ch,0)+1}) or dic, completion, {})
    
    for key, value in participant_dic.items():
        # 참가자 명단에는 있지만, 완주자 명단에 없는 사람
        if completion_dic.get(key, 0) == 0:
            answer = key
            return answer
        # 참가자명단에는 동일인물이 2명 이상이었으나, 완주자명단에는 동일인물 숫자가 그보다 1명이 적은 경우
        elif participant_dic[key] != completion_dic[key]:
            answer = key
            return answer


# 방법 2) Counter 모듈 사용
from collections import Counter
def solution(participant, completion):
    # Counter 함수를 사용해 Counter(참가자) - Counter(완주자)를 하면, 
    # Counter({'완주하지 못한 자':1})가 산출된다.
    answer = Counter(participant) - Counter(completion)
    # '완주하지 못한 자'를 반환한다.
    return list(answer.keys())[0]


# 방법 3) sort() 사용
def solution(participant, completion):
    # 참가자, 완주자 명단을 각각 오름차순으로 정렬
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        # 참가자에 동일인물이 2명 이상이나, 완주자에는 동일인물이 그보다 1명 적은 경우
        if participant[i] != completion[i]:
            return participant[i]
    # 참가자 명단에는 있으나, 완주자 명단에 없는 경우
    return participant[len(participant)-1]


# 방법 4) sort(), zip() 사용
def solution(participant, completion):
    # 참가자, 완주자 명단 각각 오름차순 정렬
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        # 참가자에 동일인물이 2명 이상이나, 완주자에는 동일인물이 그보다 1명 적은 경우
        if p != c:
            return p
    # 참가자 명단에는 있으나, 완주자 명단에 없는 경우
    return participant[-1]


# 방법 5) hash() 사용
def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        # dic 변수에 참가자 한명한명을 hash()를 통해 변환한 숫자를 key로, 참가자를 value로 설정 
        dic[hash(part)] = part
        # temp 변수에 참가자 모두를 합한 hash 숫자를 할당한다.
        temp += int(hash(part))
    # temp 변수에 있는 값에서 완주자 모두를 합한 hash 숫자를 뺀 뒤 그 값을 다시 temp에 할당한다. 
    for com in completion:
        temp -= hash(com)
    # '참가자 전원의 hash 숫자 합 - 완주자 전원의 hash 숫자 합'을 key로 갖고 있는 dic의 value를 answer에 할당한다.
    answer = dic[temp]

    return answer



if __name__ == "__main__":
    participant = ["mislav", "stanko", "ana", "mislav", "jonus"]
    completion = ["stanko", "ana", "mislav", "jonus"]
    ret = solution(participant, completion)
    print(ret)
Posted  
tags:
  • { Python }
  • { Algorythm }
  • { training }