코딩테스트 연습> 해시> 완주하지 못한 선수

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42576>

코딩테스트 연습 - 완주하지 못한 선수

 

문제설명: participant배열과 completion배열에 각각의 선수 이름들이 나열되어 있다. 해당 문제를 풀기 위해서는 2가지 케이스를 볼 수 있는데, 모두 participant에는 이름이 있지만, completion에는 이름이 없는 경우에 해당한다. 즉, 참가는 했지만 완주하지 못한 경우와, 2명의 동명이인 선수가 참가했지만, 1명만 완주를 한 경우이다. 따라서 participant와 completion 배열 내 선수 차이를 확인하면 된다.

 

[1차 시도]

def solution(participant, completion):
    for p in participant:
        if participant.count(p) != completion.count(p):
            return p

 

풀이: 제한사항 중 participant의 길이가 1 크기 때문에 participant를 기준으로 선수 한명씩의 이름을 count해서 completion과 일치 하지 않을 때 해당 선수 이름을 반환했다.

 

채첨결과: 예상대로 정확성 테스트 5개만 정상적으로 통과하고 효율성  테스트에서는 전부 시간초과가 났다.

 

해결방법: for문으로 반복을하면 participant 수 만큼 p번 수행해야하므로 시간복잡도는 O(n)이다. 따라서 데이터 개수를 셀 때 유용한 파이썬 collections 모듈의 Counter 클래스를 사용해서 해결해보았다.

 

[2차 시도]

from collections import Counter

def solution(participant, completion):
    # print(Counter(participant), Counter(completion))
    # print(Counter(participant)-Counter(completion))
    ans = Counter(participant)-Counter(completion)
    for key, value in ans.items():
        return key

 

풀이: Counter 클래스를 상용하면 배열 내 원소들의 개수를 dictionary형태로 나타낼 수 있다. 따라서 빈 dictionary를 만들어 key value로 하나씩 넣어줄 필요가 없다. 

 

예를 들어 testcase1번의 경우 첫번 째 주석 처리한 print부분을 출력하면 아래와 같이 나오는 것을 확인 할 수 있다.

 

Counter({'leo': 1, 'kiki': 1, 'eden': 1}) Counter({'eden': 1, 'kiki': 1})

 

이를 다시 Counter들끼리의 차를 구할 수 있는데, 두 번째 주석 처리한 print를 출력하면 아래와 같이 나온다.

 

Counter({'leo': 1})

 

즉, 알아서 개수의 차이가 있는 key와 value를 반환한다. 

 

따라서 결과를 ans에 담아 for문으로 items내 key와 value값을 찾아 key값만 return 한다.

 

 

채첨결과: 정확성과 효율성 테스트 모두 정상적으로 잘 통과한다.