취업 리부트 코스 3주차(2) - 우선순위 큐 heap과 해시테이블

처음 사용해본 자료구조 우선순위 큐! 풀었던 문제 몇가지와 멘토님이 추천해주신 문제를 정리하자.

백준 9375번: 패션왕 신해빈

이 문제는 거의 경우의 수 공식을 이용한 느낌이다.

풀이 1. dict 사용

# 1. 이중 for문으로 입력받아서 옷 구성을 함수로 전달
# 2. 옷 구성 = [('hat', 'headgear')]
# 3. 옷 구성의 2번째 값을 dict의 key값으로, 가짓수를 +1씩
# count -> {'headgear': 2, 'eyewear': 1}
# 경우의 수 공식 (a1 + 1)* (b1 + 1) ... - 1

from collections import defaultdict

test_case = int(input())

def count_combi(outfits):
    count = defaultdict(int)
    # 2, 3번
    for o in outfits:
        count[o[1]] += 1

    # 경우의 수 구하는 공식
    result = 1
    for key in count:
        result *= (count[key] + 1)
    return result - 1

for _ in range(test_case):
    n = int(input())
    outfits = []
    for _ in range(n):
        name, category = input().split()
        outfits.append((name, category))
    print(count_combi(outfits))

풀이 2. Counter로 카테고리의 개수 세기

from collections import *

test_case = int(input())
for _ in range(test_case):
    n = int(input())
    outfits = []
    
    for _ in range(n):
        _, category = input().split()
        outfits.append(category)
        counter = Counter(outfits)

    #Counter({'headgear': 2, 'eyewear': 1})
    
    result = 1
    for c in counter.keys():
        result *= (counter[c] + 1)
    print(result - 1)

백준 11286: 절대값 힙

-1, -2, -3 이 있을때 -1부터 출력하려면 대체 어떻게 할지 고민했다. 출력할 때 건들 수 있는 부분이 아닌거같아서 찾아보니 heap에 담을 때, 튜플로 절대값과 원래값을 함께 담는 풀이였다!

heapq는 (1,-1)과 (2,-2)가 있다면 튜플의 첫번째 원소로 최소값을 고르기에 -1에 해당하는게 먼저 heappop() 된다는 것을 알았다. 더불어 if else문 간결하게 쓰는것도 눈에 조금 익어가니 사용에도 익숙해지면 좋을듯..!

from heapq import *
from sys import stdin
input = stdin.readline

n = int(input())
heap = []

for _ in range(n):
    num = int(input())
    if num: # 0이 아니면
        heappush(heap, (abs(num), num))
    # 0이라 출력
    else: 
        if heap:
            print(heappop(heap)[1])

        else: # 빈 배열이라면
            print(0)

from heapq import *
from sys import stdin
input = stdin.readline

n = int(input())
heap = []

for _ in range(n):
    num = int(input())
    if num:
        heappush(heap, (abs(num), num))
    else:
        answer = heappop(heap)[1] if heap else 0
        print(answer)

멘토님이 추천하신 heap 문제!

백준 1715번: 카드 정렬하기

백준 7662번: 이중 우선순위 큐