프로그래머스에서 완주하지 못한 선수 문제를 풀었다. 인형 뽑기 문제를 풀고와서 그런지 굉장히 쉽게 느껴졌는데, 효율성 테스트라는 엄청난 난관이...?
문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
첫 번째 접근
리스트 메소드를 정리한 뒤인지라 sort를 써보려다가, 참가자 리스트를 반복문으로 돌려서 만약에 참가자 a의 수가 완주자 a의 수보다 많으면(동명이인 고려) 해당 값을 리턴하는 로직을 짰다.
답은 바로 나왔는데 효율성 테스트에서 완전히...다 실패해부렀다 😭 아직 시간복잡도가 낮은 코드에 대한 인지가 부족하다.
def solution(participant, completion):
for p in participant:
if participant.count(p) > completion.count(p):
return p
두 번째 접근
원래는 리스트끼리 빼보려고 했는데... 될 리가 없지! 그래서 참가자, 완주자 중에서 중복을 제거해줄 수 있는 set으로 만든 다음에 빼줘보았다.
set은 다른 말로 집합 자료형이라고 부른다. 집합에 관련된 것을 쉽게 처리하기 위해 만든 자료형이기 때문에, 차집합, 교집합, 합집합을 만들 때 매우 유용하다. 중복이 없고, 순서도 없어서 indexing은 불가하지만, 리스트와 다르게 data끼리 더하고 빼는 것들이 가능하다.
이 상황에서는 동명이인 체크는 불가하지만 구하고자 하는 return값이 동명이인이 없을 경우는 답을 낼 수 있다. 그런데 이마저도 효율성 테스트에서 하나가 실패가 떴다 🥺
def solution(participant, completion):
player = list(set(participant)-set(completion))
if player:
return player[0] 
세 번째 접근
첫 번째랑 두 번째 코드를 합쳤더니 마지막 테스트 5빼고 통과가 떴다. 효율성 테스트가 단순히 코드를 간결하게 쓰는 문제가 아니라, 간단한 조건에 대해서 1차적으로 걸러주고 그 다음 복잡한 조건을 차례대로 걸러주는 것들을 테스트하는 것 같다. (명시가 되어있으면 좋겠지만 그저 내 추측)
여튼 그래서 두 번째 접근에서 조금 더 시간이 적게 걸리는 방법을 찾아야 한다.
마지막
결국 구글링을 했고...! 정렬을 한다음에 짝을 지어서, 다른 애를 return하는 답변으로 제출했다. 원래 처음 접근할 때 sort를 사용하긴 했는데 짝지어주는 것까지는 고려를 안 했던 것 같다.
좀 찜찜한 것은 전체적으로 답변 제출 시간이 늘어났다는 것..? 테스트 케이스를 좀 보여주면 좋을텐데 🤔
def solution(participant, completion):
participant.sort()
completion.sort()
for p,c in zip(participant, completion):
if p != c:
return p
return participant.pop()
zip : 배열을 같은 인덱스끼리 짝지어준다. 만약 배열의 길이가 다를 경우 같은 인덱스끼리만 짝지어주고, zip 객체에서 나머지 인덱스는 제외된다.
>>> a = [1,2,3,4,5]
>>> b = [1,2,3,4]
>>> zip(a,b) # zip(a,b)를 shell에 찍으면 객체 <zip object at 0x104a3e960>가 나옴
>>> for a in zip(a,b):
... print(a)
# a의 마지막 인덱스 5는 제외되어 있는 것을 알 수 있다.
(1, 1)
(2, 2)
(3, 3)
(4, 4)다른 사람의 풀이에서 가장 좋아요를 많이 받은 답변은 collections였다. collection 모듈이 브랜디에서 인턴할 때도 되게 유용하게 쓰였었는데 한 번 정리를 해야겠다.
