[프로그래머스 Level1] 완주하지 못한 선수 with 파이썬

문제

https://programmers.co.kr/learn/courses/30/lessons/42576

풀이

participant와 completion 배열이 입력되는데 얘네는 문자열로 이루어져 있다. 제한사항을 확인해보면 선수의 수는 1 이상 100,000 이하이다. 따라서 문자열을 다룰때 배열을 만들어서 정렬하여 카운트 한다고 하면 시간 복잡도는 엄청나게 커질것이다. 그래서 이런 문자열을 가지고 카운트를 할때는 해시를 이용하는 게 좋다.

해시는 시간 복잡도가 상수에 비례하기 때문에 빠르게 계산할 수 있다. 해시의 사용법만 안다면 쉽게 해결할 수 있는 문제이다.

문제의 함정은 동명이인이 있다는 건데, participant 배열에 있는 각 선수들을 키 값으로 해서 해시에 넣고 선수 이름이 나오는 만큼 값을 1씩 더해주면 된다. 그 다음에 completion에 있는 선수들을 하나씩 꺼내보면서 해시의 키 값으로 검색해주고 해당되는 값을 1씩 뺀다면 한 명만 남게 될것이다. 결론적으로 계산이 끝났을때 값이 1 인 키를 찾아서 출력해주면 끝.

코드

다른 풀이

많은 사람들은 이 방법으로 풀었다. 각 배열을 정렬한 후에 첫 값부터 비교해보면서 만약에 값이 다르다면 participant에서 해당 값을 출력하는 것이다. 알파벳 순으로 정렬되기 때문에 정답은 나오고 테스트도 통과되지만 시간복잡도가 O(NlogN) 이기 때문에 해시를 사용한 것보다 비효율적이라고 할 수 있다.