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

Yebin Lee·2022년 9월 24일

코테준비

목록 보기

11/12

거진 한 달 만에 velog를 찾은 것 같다 ... 그동안 공부를 별로 안했다면 안 한 것도 사실인데 ^^;; 3학년 2학기를 지내면서 고민이 많은 것 같다. 이렇게 해서 취업을 할 수 있을지, 내가 하고 있는 방식이 맞을지.

잠시 생각을 보류하고 현재에 내린 결론은 어쨌든 이번 학기는 마칠 터이니 뭐든 열심히 해보자는 것이다. 오늘은 노션에 틈틈이 정리해놨었던 문제를 들고 와봤다. 노션에 정리해놓고 velog 에 기록하며 되짚어보는 것이 더 나은 방법이라 판단했다. 물론 시간은 더 걸리지만, 그만큼 시간을 더 투자해야 내 것으로 만들고, 내가 얻을 수 있는 것이라 생각한다.

프로그래머스 [완주하지 못한 선수] 문제 보기

오빠랑 코테 준비를 꾸준히...! 하기로 했기에 열심히 공부해봤다. 아직은 정말 많이 부족하지만 이번 학기에는 꼭 알고리즘을 하나씩 돌파해나갈 예정이다.

프로그래머스 [완주하지 못한 선수] 문제 풀이

내 풀이

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

participant 와 completion 을 모두 정렬하고 zip으로 묶어서 두 가지를 서로 비교

같지 않다면 해당 participant 가 완주하지 못한 선수이므로 반환

완주하지 못한 선수는 무조건 한 명인데 루프를 돌면서 값이 나오지 않았다면 결국 sort 된 후 마지막에 있는 주자가 답이 되므로 participant[-1] 을 반환

zip

numbers = [1, 2, 3]
letters = ['a', 'b', 'c']

for pair in zip(numbers, letters):
		print(pair)

# result
(1, 'a')
(2, 'b')
(3, 'c')

다른 풀이

Hash 를 이용하는 방법

사실 이 문제는 Hash 항목에 있는 것을 보아 이 방법대로 푸는 것이 정석… 일 것임

처음에는 왜 굳이 더 어렵게 풀어야 하지? 라는 생각을 했는데 이 문제가 쉬우니까 다른 쉬운 방법이 있었던 거지, 비슷한 유형의 어려운 문제가 출제된다면 Hash 로 푸는 것이 맞다고 판단했음

결론은 ~ Hash 공부를 합시다 ~

hash 를 모르니까 남이 구현한 코드를 봐도 이해할 수가 없었다 … 그래서 공부함

Hash 를 사용하기 좋을 때 (3가지 경우)

해시는 딕셔너리를 통해 제공됨

딕셔너리 함수의 시간복잡도는 대부분 O(1) 이라 사용하기 좋음

리스트를 사용할 수 없을 때
리스트는 list[1] 은 가능하지만 list[’a’]는 불가
인덱스 값을 숫자가 아닌 문자 혹은 튜플로 사용하고 싶으면 딕셔너리를 사용하는 것이 좋음
빠른 접근 혹은 탐색이 필요할 때
딕셔너리 함수의 시간복잡도는 대부분이 O(1) 이라서 …?
집계가 필요할 때
원소의 개수를 셀 때 collections 의 Counter 와 함께 사용하면 편리

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

collections.Counter 를 이용하는 방법

import collections

def solution(participant, completion):
		participant.sort()
		completion.sort()

		result = collections.Counter(participant) - collections.Counter(completion)

		return list(result)[0]

정렬 후 collections의 Counter 로 participant 에서 한 명을 남기고 list 로 변환하여 그 list 의 첫 번째를 반환 (list 에는 하나가 남아있음)

collections 의 Counter

import collections
lst = ['aa', 'cc', 'dd', 'aa', 'bb', 'ee']
print(collections.Counter(lst))

# result
Counter({'aa': 2, 'cc': 1, 'dd': 1, 'bb': 1, 'ee': 1})