[프로그래머스] 완주하지 못한 선수 python/파이썬 (4가지 솔루션)

첫번째 솔루션

배열 정렬 할 수 있다는 특성을 이용했다.

participant과 completion 배열을 정렬 할 경우 완주하지 못한 참가자를 제외하면 completion과 일치해야한다는 점을 이용했다. 완주하지 못한 선수가 1명 이상이더라도 위의 개념을 이용해서 해결 할 수 있다.

 

python 내부 함수 sort 정렬 과정에서 O(N log N)

반복문 O(N)

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

 

두번째 솔루션

해쉬테이블(java), Dictionary(python)의 개념을 이용했다.

첫번째 솔루션도 만족스러웠지만 해쉬 카테고리의 문제였기 때문에 문제 의도에 맞게 풀어보려했다.

동명이인이 있다는 점이 해쉬 key값에 살짝 까다로울 수 있지만 조건문을 추가해주면 어렵지 않게 해결 할 수 있다.

 

이또한 완주하지 못한 선수가 1명 이상이어도 문제 없이 해결 할 수 있다.

 

해쉬를 사용하기 때문 dic.get()은 O(1)이다. 따라서 모든 반복문은 O(N)이다.

 

여담으로 파이썬을 공부할겸 문제를 푸는데  if --dic[comp] == 0: 으로 짜고 싶었지만 파이썬에는 후위, 선위 개념이 없다는걸 알았다.

def solution(participant, completion):
    answer = ''
    dic = {}
    for part in participant:
        dic[part] = dic.get(part, 0)+1
    for comp in completion:
        if dic[comp]-1 == 0:
            del(dic[comp])
        else:
            dic[comp] -= 1
    answer = dic.keys()

    for answer in list(answer):
        answer = answer
    return answer

 

 

(세번째 솔루션, 네번째 솔루션은 다른 사람의 코드이기 때문에 코드 없이 설명한 쓰겠다.)

 

세번째 솔루션

[다른 사람의 풀이]  맨 위에 있는 코드

collections.Counter를 사용하는 코드이다. Counter객체는는 Dictionary와 다르게 빼기 연산이 가능하다(집합의 뺄셈). 이를 이용해서 비약적으로 짧은 코드를 작성이 가능하다. 단순하게 배열을 Counter객체로 변환한 후 participant-completion만 해주면 된다. (놀랍다)

 

당연히 미완주자가 1명 이상인 경우에도 풀이가 가능하다.

 

네번째 솔루션

[다른 사람의 풀이]  두번째에 있는 코드

(hashtable) Dictionary를 이용하지만 본문의 두번째 솔루션과는 살짝 다르다. tmp라는 임시 변수를 사용하여 모든 participant를 순회하며 participant값을 hash값으로 변환해주고 이를 Dict에 키값으로 사용하여 해당 hash값에 participant 값을 value로 넣어준다. 이와 동시에 tmp변수에 모든 hash값을 더해준다

이후 completion을 순회하며 모든 값을 hash값으로 변환하며 이를 tmp에서 빼준다.

 

tmp = (participant 모든 값을 hash로 변화하여 더한 값) - (completion 모든 값을 hash로 변환하여 더한 값)

즉 tmp는 완주하지 못한 1명의 hash값 만이 남게된다. tmp값을 이용해 Dict[tmp]를 통하여 선수 이름을 가져온다.

 

굉장히 기발한 풀이이다. 하지만 이를 보고 이해하는데 조금 시간이 필요했고 hash값이 꼬일 수 있는 위험성도 있다. 참여자가 2명 이상일 경우 해결이 불가능하다. 해당 문제에만 특화된 코드라고 볼 수 있지만 이런 접급법도 있다고 생각해둘만한 풀이같다.