커뮤러닝(1주차) - 완주하지 못한 선수 in python

 

이 문제는 예전에 프로그래머스 1단계 깨기 할 때 풀었던 문제라서 쉽게 풀었다. 

 

1. 문제설명

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

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

 

* 제한사항

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

* 입출력 예

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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

2. 풀이

이 문제에서 가장 핵심은, 참가자의 숫자보다 완주자가 1이 작다는 점,

그리고 동명이인이 있을 수 없다는 점 두가지이다.

 

두 배열을 비교해서 포함되지 않은 이름을 고르면 된다. 

1) 먼저 배열 안에서 알파벳 순으로 확인할 수 있게 participant와 completion을 sort()를 사용해서 정렬한다.

2) 이미 정렬이 되어있는 상황으로 참가자와 완주자에서 인덱스에 같은 값이 나와야 한다. 인덱스가 같은데 다른값이면 참가자는 완주를 못한 것이므로 참가자의 값을 리턴한다.

3) 완주자가 포문을 다 돌았는데도 다른 값이 없으면 참가자의 배열 맨 마지막 인덱스 값이 미완주이므로, participant[-1]이 미완주자이다.

 

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        # 배열을 정렬했으므로 같은 인덱스로 값이 나오지 않을 경우, 참가자에서 해당 인덱스 값을 리턴
        if(participant[i] != completion[i]):
            return participant[i]

    # 전체를 비교했는데, 다른 값이 없을 경우 참가자의 맨 마지막 값이 없는 경우이므로 길이의 -1로 리턴
    return participant[-1]

print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))

 

** 이 문제는 해쉬문제라고 적혀있었으므로, hash를 이용해서 문제를 추가로 풀어보았다.