[프로그래머스] - 해시 . 완주하지 못한 선수

안녕하세요.

오늘 해시 문제를 다 풀고 잠에 들 예정입니다 ..

 1번 문제는 풀고 나서 그냥 바로 2번 문제로 넘어갔습니다. 2번 문제부터는 ..뭔가 다른 사람들의 풀이가 궁금해서 한번 봤더니 .. 뭔가 분해서 블로그에 남겨야겠습니다 .... ㅜ

 

짧은 코드가 반드시 좋은 코드라고 할 수는 없지만 .. 저는 약 20줄에 걸친 코드를 단 2?줄에 푼 사람들을 보니 배가 아파서요 ... 

 

문제

 

풀이

 

우선 이 문제를 왜 해쉬로 풀어야하는가에 대해 고민을 해보았습니다. 

맨 처음에는 그냥 차례대로 정렬해서, 하나씩 값을 비교해보면 되는게 아닌가? 하는 생각 때문에 계속의아했는데요 ..

아무래도 해시를 쓰는 이유는 시간 복잡도의 이유 때문인 것 같습니다.

그래서 그냥 dictionary에 참가자를 집어넣고, key 중복이 발생하면 data 값을 하나 올려서 우선 저장을 합니다.

그 이후에 완료한 사람의 이름을 dictionary에서 search 하고, 1명일 경우 삭제해나가서, 최후에 dictionary에는 완료한 사람의 배열에 없었던 사람의 이름만 남도록 하였습니다.

나의 코드

def solution(participant, completion):
    
    dictionary = {}

    for i in participant:
        if i in dictionary :
            dictionary[i] = dictionary[i] + 1
        else:
            dictionary[i] = 1

    for i in completion:
        if dictionary[i] <= 1:
            dictionary.pop(i)
        else:
            dictionary[i] = dictionary[i] - 1
                
    for key in dictionary.keys():
        answer = key
    return answer

다른 사람 코드

import collections


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

 

 

그런데 왠걸 ... 답을 보니 다른 사람들은 collections 을 사용해서 정말 간편하게 풀었더군요 ... 

그래서 다음부터는 저도 collection 을 이용해서 풀 수 있도록 여기에다가 정리해놓겠습니다 !!!

 

 

아래에 작성해가는 Counter 문법은 https://sulmasulma.github.io/algorithm/2020/05/12/collections.html을 보고 작성하였습니다.

 

collections... 니 누고 ....

 

 

collections는 파이썬 알고리즘을 풀 때 유용한 라이브러리 중 하나입니다. 당연히 코딩 테스트에서도 사용 가능한 python 표준 라이브러리 중 하나로, stack과 queue 자료구조를 구현 할 수 있습니다.

 

1. Counter

 

list, tuple 등을 Counter Dictionary 로 바꾸어주는 클래스입니다. 인자로 받은 배열의 각 값이 몇개 있는지 반환 합니다.

 

from collections import Counter

lst = [1, 2, 3, 3, 2, 1, 1, 1, 2, 2, 3, 1, 2, 1, 1]
counter = Counter(lst)
print(counter)
# >>> Counter({1: 7, 2: 5, 3: 3})

 

또한 Counter에는 가장 개수가 많은 n개 값을 list로 반환하는 .most_common() 메소드가 있습니다.

 

print(counter.most_common(2))
# >>> [(1, 7), (2, 5)]

 

2. Defaultdict

 

defualtdict 는 python dictionary와 유사하지만, 존재하지 않는 key에 접근해도 에러가 출력되지 않습니다.

 

from collections import defaultdict

names_dict = defaultdict(int)
names_dict["Bob"] = 1
names_dict["Katie"] = 2
sara_number = names_dict["Sara"]
print(names_dict)
# >>> defaultdict(<class 'int'>, {'Bob': 1, 'Katie': 2, 'Sara': 0})

 

defaultdict 객체의 기본 형식으로 int 를 지정합니다.

key와 그에 맞는 value를 지정한 Bob, Katie에는 값이 나오지만, key를 지정하지 않은 Sara에 대해서는 int의 기본 값인 0이 할당됩니다.

 

위 코드에서 defaultdict 의 기본 형식으로 int 대신 list를 지정하면 , 즉 names_dict = defaultdict(list) 로 바꿔주면 Sara의 값은 아래와 같이 빈 list가 됩니다.

 

defaultdict(<class 'list'>, {'Bob': 1, 'Katie': 2, 'Sara': []})

 

3. deque

 

python에서 list는 stack입니다. 한 쪽에서 입출력이 모두 일어나는 First-In-Last_Out 자료구조죠.

라이브러리 deque는 stack과 더 불어 queue 까지 구현 할 수 있습니다. 한쪽에선 입력, 반대 쪽에선 출력이 되는 First-In-First_Out 자료구조입니다.

 

• deque는 기본적으로 최대 길이를 설정할 수 있습니다.

from collections import deque

my_queue = deque(maxlen=10)
for i in range(10):
    my_queue.append(i+1)
print(my_queue)
# >>> deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], maxlen=10)

my_queue.append(11)
print(my_queue)
# >>> deque([2, 3, 4, 5, 6, 7, 8, 9, 10, 11], maxlen=10)

• 처음에 1부터 10까지의 값이 들어가도록 했습니다. 최대 길이를 10으로 설정했기 때문에 11이 들어가려고 할 때, 가장 앞에 있던 값인 1이 빠지게 되는 queue 자료구조입니다.

 

stack 처럼 사용하려면 어떻게 해야할까요?

 

• .pop() 메소드를 사용하면 됩니다.

stack = deque()
for i in range(10):
    stack.append(i+1)

stack.pop()
print(stack)
# >>> deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

• stack.pop()을 출력하면 꺼낸 element가 나오고, 이 element를 stack에서 꺼낸 것이므로 stack을 다시 출력하면 element가 제외됩니다.

 

queue구조로 사용하기 위해서는 다음과 같은 함수를 사용할 수 있습니다.

 

• .popleft() 메소드를 사용하면 됩니다.

queue = deque()
for i in range(10):
    queue.append(i+1)

queue.popleft()
print(queue)
# >>> deque([2, 3, 4, 5, 6, 7, 8, 9, 10])

• queue.popleft() 를 출력하면 꺼낸 element가 나오고, 이 element를 queue에서 꺼낸 것이므로 queue를 다시 출력하면 element가 제외됩니다.

 

다음 번에는 꼭 ! Collections를 활용해서 해시 문제를 풀어보겟슴다