[프로그래머스] Lv1 완주하지 못한 선수

회고

이번 문제풀이는 알고리즘의 시간 복잡도에 대해서 좀 더 생각해보는 계기가 되었다.

시간복잡도를 생각하지 않고, 문제를 풀이할 경우 어떻게든 풀이가 가능했다.
하지만 체점에 있어서 효율성측면에서 시간초과가 발생하는 것으로 보아 시간복잡도 측면에서 문제가 발생했다는 것을 알았다.

문제에서 제기한 문제풀이 방법은 해시를 이용한 풀이이고 해시의 시간복잡도는 O(1)의 시간복잡도이며 최악의 경우 O(n)이다.

또한 문제에서 제기한 100,000명의 최대값의 경우 O(NlogN)의 복잡도가 마지노선이 된다.

문제풀이에 해시를 이용해야 한다는 점은 알았으나 결국 해시를 이용한 풀이는 하지 못했다...

다른 풀이 방법으로 collection의 Counter함수를 이용해서 문제풀이를 했다.
Counter()는 인자로 주어지는 리스트내의 동일 요소가 몇개가 있는지 딕셔너리 형태의 Counter()객체를 반환한다.

이점을 이용해서 문제를 풀이했다.

풀이

from collections import Counter
def solution(participant, completion):
    new_part = Counter(participant)
    new_comp = Counter(completion)
    print((new_part- new_comp).keys())
    for i,j in new_part.items():
        if abs(new_comp[i] - j) != 0:
            return i

def solution(participant, completion):
    new_part = Counter(participant)
    new_comp = Counter(completion)
    return list((new_part- new_comp).keys())[0]
    


participant = ["mislav", "stanko", "mislav", "ana"]
completion = ["stanko", "ana", "mislav"]
a = solution(participant, completion)
print(a)

Counter함수를 이용해서 각 요소에 대한 카운트를 딕셔너리 형태로 받아서 두개의 변수의 카운트를 한쪽에서 빼서 만약 0이 아니라면 해당 요소가 풀이의 해답이 되는 코드 구현이다.

풀이참조

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
        
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]
    
    return answer

   

위의 코드는 다른 사람의 풀이를 복사해온것으로 해시를 이용한 풀이이기에 참조하고자 했다.

처음 for문을 돌면서 해시를 이용해서 딕셔너리 형태로 해시값과 벨류를 저장한다. temp라는 변수는 위치의 해시값들을 모두 더함으로써 위치를 특정하기 위한 변수로 보인다.

다음 for문에서 temp에서 hash로 변환한 값들을 빼줌으로써 결과로 남은 temp의 hash값에 해당하는 벨류를 반환값으로 리턴하는 것으로 문제풀이를 했다.