[Coding Test] Programmers_완주하지 못한 선수

이런 부분은 이렇게 사용했으면 좋겠다! 싶거나 추가했으면 하는 내용은 과감히 댓글 부탁드립니다.

 

[완주하지 못한 선수]

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

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

 

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

• completion의 길이는 participant의 길이보다 1 작습니다.

• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

• 참가자 중에는 동명이인이 있을 수 있습니다.

 

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

input example [participant], [completion]:
["leo", "kiki", "eden"], ["eden", "kiki"]

output:
"leo"

 

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

input example [participant], [completion]:
["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]

output:
"vinko"

 

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

input example [participant], [completion]:
["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]

output:
"mislav"

 

---

동명이인이 없었다면 문제는 아래 코드로 간단하게 해결할 수 있었을겁니다.

def solution(participant, completion):
    answer = []
    answer += [i for i in participant if i not in completion]
    return answer

 

고려해야 할 요소는 고려해야죠. copy 모듈을 이용해 answer는 participant의 deep copy를 진행했어요.

list compresions를 이용해 participant의 참가자가 completion 내의 완주자로 존재한다면 해당 선수를 지웠어요. 하나씩 지워가다보면 결국 완주하지 못한, 동명이인도 마찬가지로 남게돼죠. 

import copy

def solution(participant, completion):
    answer = copy.deepcopy(participant)
    [(answer.remove(i), completion.remove(i)) for i in participant if i in completion]
    return ''.join(answer)

 

문제는 해결했지만 효율적인 면에 대해서 계속 고민했습니다. 애초에 participant의 원소로 비교하는 필요는 없더라구요. 변한 코드의 모습은 이렇습니다.

def solution(participant, completion):
    completion.sort(); participant.sort();
    for i in completion:
        participant.remove(i)
    return ''.join(participant)

 

완주자(completion)의 선수로 참가자(participant)에 해당하는 원소를 삭제합니다. 그럼 더욱 간단하고 빠른 코드가 나오게 돼죠.

초반 라인을 보시면 각 리스트를 정렬하는데, 이는 코드 실행시간에 큰 차이를 일으킵니다. 정렬을 넣었을 때와 넣지 않았을 때의 실행 시간을 비교한 내용을 봐주세요.

[Yes정렬]

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.26ms, 10.8MB)
테스트 4 〉	통과 (0.54ms, 11MB)
테스트 5 〉	통과 (0.55ms, 10.9MB)


[No정렬]

테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.04ms, 10.8MB)
테스트 3 〉	통과 (0.80ms, 10.9MB)
테스트 4 〉	통과 (2.97ms, 11MB)
테스트 5 〉	통과 (2.78ms, 11MB)

한 눈에 봐도 큰 속도차이를 보이죠.

 

해당 코드로 만족하던 중 고수 한 분의 collections 모듈 언급을 보았습니다. 적용하니 너무나 획기적인 코드로 변신했어요! 수행시간 또한 월등합니다.

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return ''.join(answer.keys())

테스트 1 〉	통과 (0.08ms, 10.7MB)
테스트 2 〉	통과 (0.07ms, 10.8MB)
테스트 3 〉	통과 (0.25ms, 10.8MB)
테스트 4 〉	통과 (0.42ms, 11MB)
테스트 5 〉	통과 (0.41ms, 11.1MB)

 

 

HyunJin-Jeong/Practice_CodingTest-Python