프로그래머스 Level 1) 완주하지 못한 선수

문제 설명

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

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

 

---

문제 해설

참가자 명단과 완주자 명단을 비교했을 때, 완주자 명단에 없는 사람을 찾으면 된다. 

근데 제한 사항에 참자가와 완주자 리스트의 길이가 1 차이나므로, 완주하지 못한 사람은 한명밖에 없다는 것이다. 

즉, 완주자 명단에 없는 한 명을 찾으면된다. 

이렇게만보면 문제가 쉬운것 같지만, 두 리스트를 비교함에 있어서 효율성을 통과해야한다. 

 

 

 

내가 처음 푼 방법

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

    return participant[0]

정답은 다 맞지만 효율성에서 다 시간초과가 됐다. 이부분을 생각하지 못했던 나..ㅠㅠ

 

 

 

정답

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

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

리스트 구조에서 어디에 있는지도 모르는 특정 데이터를 찾는 것은 시간이 비교적 오래 걸린다. 

따라서 정렬을 하면 처음 정렬하는데 시간을 쓰지만 그 이후 찾을 때는 매우 효율적이기 때문에, 처음에 정렬을 한다. 

 

또한 막연히 찾는것보다 인덱스로 찾는것이 훨씬 빠르기때문에 for in으로 있는지 없는지 찾는게 아닌, 

인덱스를 사용해서 찾는 방법을 선택한다. 

 

인덱스로 비교해서 마지막까지 완주하지 못한 1명을 못찾았을 경우,

제일 마지막에 있는 참가자가 답이므로 return participant[-1]을 한다. 

 

 

 

 

이번 문제를 풀면서 느낀점. 

코드가 무조건 간결한게 좋은 코드가 아니라 알고리즘과 데이터 구조에 따라 코드가 길더라도 효율성을 고려해야겠다는 생각을 했다. 그동안 코드가 짧으면 무조건 좋아보였는데, 알고리즘 공부의 중요성을 많이 느꼈다. 

비전공자여서 놓치기 쉬운 부분인것같은데 이번기회로 빅 오 표기법 등 효율성을 위한 공부를 해야겠다고 생각했다.