프로그래머스 1단계 문제인 '완주하지 못한 선수' 문제를 풀어보았다.

문제

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

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

---

내 풀이

내 풀이 1(실패)

아래는 participant에 있는 사람이 completion에 있지 않으면 그 사람의 이름을 출력하는 코드이다. 이렇게 풀고 싶었지만, 사람의 이름으로 분별하기 때문에 중복된 이름이 나오면 판별할 수 없어서 실패했다.

print([x for x in participant if x not in completion])

내 풀이 2(실패)

completion에 있는 이름을 participant에서 for문을 돌며 하나씩 지우고, 하나 남는 이름을 리턴하려고 했지만 시간 초과로 실패했다.

def solution(participant, completion):
    for c in completion:
        participant.remove(c)

    for p in participant:
        return p

내 풀이 3(실패)

이 풀이는 딕셔너리를 사용해서 풀어보려고 했다. 일단 리스트를 딕셔너리 형태(사람 이름: 명수)로 만들긴 했는데 여기서 어떤 연산을 해야할지 모르겠다. --> 더 공부해서 추후 업데이트 예정

# {'mislav': 1', stanko': 1, 'ana': 1}
c_dict = {}
for c in completion:
  c_dict[c] = completion.count(c)

# {'mislav': 2, 'stanko': 1, 'ana': 1}
p_dict = {}
for c in participant:
  p_dict[c] = participant.count(c)
 

---

다른 풀이

다른 풀이 1

아예 정렬을 해두고, 하나씩 비교하며 같은 인덱스일 때 다른 사람이 존재하면 그곳의 인덱스에 있는 사람을 answer로 반환했다.

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

예) participant에 mislav가 두 명 있고 completion에 mislav가 한 명 있으므로 mislav가 답이다.

participant와 completion을 정렬해놓았을 때, 둘의 인덱스 2가 다르므로 participant[2]가 미완주자로 반환된다.

participant = ['ana', 'mislav', 'mislav', 'stanko']
completion = ['ana', 'mislav', 'stanko']
mislav(리턴값)

다른 풀이 2

해시(키:값으로 이루어진 구조)를 사용했다.

먼저 dict({})를 만들고, 거기에 participant의 원소들을 할당했다. 그리고 각 원소들에 hash()를 하여 해시값을 hashValue에 계속하여 더했다.

이렇게 하면 participant의 모든 원소의 해시값이 더해진다.

그리고 completion에서 원소를 하나씩 가져와 해시값을 hashValue에서 하나씩 뺐다.

그러면 이제 누락되거나 중복된 값의 해시값이 하나 남고, 그 값을 d[hashValue]로 리턴하면 된다.

def solution(participant, completion):
    d = dict()
    hashValue = 0
    for p in participant:
        d[hash(p)] = p
        hashValue += hash(p)
    for c in completion:
        hashValue -= hash(c)
    return d[hashValue]