[프로그래머스] 완주하지 못한 선수2

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

프로그래머스

 

[문제 설명]

 

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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):
    participant.sort()
    completion.sort()
    for idx in range(len(completion)):
        if participant[idx] != completion[idx]:
            return participant[idx]
    return participant[-1]

며칠전 효율성 테스트에서 실패했던 문제.

처음 풀었던 방법과 같은 방법을 사용했는데, count함수 대신 sort메서드와 idx를 사용해 접근하였다.

 

[마음에 든 방법]

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]
    return answer

해시함수를 사용하였다.

1. temp변수에 participant 배열의 모든 요소의 해시값을 더한다.

2. 그 다음, temp변수에서 completion 배열의 모든 요소의 해시값을 뺀다.

3. 남은 해시값에 해당하는 값을 반환한다.

 

해시함수는 입력값에 대한 길이에 상관없이 일정한 길이의 비트열로 반환해주는 함수이다.

해시함수는 입력값을 해시테이블에서 찾아서 출력값으로 해당 테이블 주소를 반환한다.

따라서, 입력값의 길이가 다르더라도 출력값의 길이는 항상 일정하다.

 

이 방법을 사용하여 해당 문제를 푼 것이다.

 

알고리즘 문제를 잘 풀기 위해서는 자료형 및 시간복잡도에 대한 이해가 중요한 것 같다.

우선 자료형에 대한 공부부터 해야겠다.