minzzl
[프로그래머스] - 해시 . 완주하지 못한 선수 본문
안녕하세요.
오늘 해시 문제를 다 풀고 잠에 들 예정입니다 ..
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를 활용해서 해시 문제를 풀어보겟슴다
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스] - 정렬. K번째 수 (0) | 2023.04.20 |
---|---|
[프로그래머스] - 스택/큐. 기능개발 (0) | 2023.03.06 |
[프로그래머스] - 스택/큐.같은 숫자는 싫어 (0) | 2023.03.06 |
[프로그래머스] - 해시.전화번호 목록 (0) | 2023.02.28 |