[Map, Set, Priority Queue] 💡 BOJ - 1620번, 14425번, 11279번, 2075번, 4358번, 11286번, 7662번, 21939번, 2696번, 21942번

자료구조별 연습

0️⃣ Map

# 선언방법
dictionary = {} or dict()

# 딕셔너리 for 문
# 1. 일반적으로 for문을 돌리면 key값이 순회된다.
	for key in a:
		... 
# 2. value값을 순회하기위해서는 values()를 사용
	for value in a.values():
		...
# 3. key와 value를 한꺼번에 순회하려면 items()를 사용
	for key, value in a.items():
		...
# 4. dictionary에서 in 값은 key값에 한해서 동작
# 5. 딕셔너리의 요소 삭제
a = {'alice': [1, 2, 3], 'bob': 20, 'tony': 15, 'suzy': 30}
del a['alice']

>>>

{'bob': 20, 'tony': 15, 'suzy': 30}

1️⃣ Set

s = set()
# 1. set과 list, tuple은 서로 형변환이 예쁘게 가능

# 2. 교집합, 차집합, 합집합
	# 1) 교집합
		s1 & s2
	# 2) 차집합
		s1 - s2
	# 3) 합집합
		s1 | s2

# 3. 값을 추가하는 경우
	# 1) 하나만 추가하는 경우
		s.add(value)
	# 2) 여러개를 추가하는 경우
		s.update(list)

# 4. 값을 제거하는 경우
	    s.remove(value)

2️⃣ Priority Queue

* 힙, 이진 트리 모양, 부모가 자식보다 크거나 (최대 힙) 작아야 (최소 힙) 한다.

* pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐 

* 원소 추가 시 O(logn) (heapify 때문)

* 우선순위가 가장 높은 원소의 확인이 O(1) - 그냥 인덱스 0번 읽으면 된다.

* 원소 삽입 과정 - O(logn) 

* 우선순위가 가장 높은 원소의 제거는 O(logn) - 마지막 원소와 바꾸고 삭제 O(1) + heapify 과정 다시 O(logn)

* 파이썬에서는 기본 최소힙으로 구현되어 있다. 

import heapq
<min Heap 형태>
heap = []
# 삽입
	heapq.heappush(heap, 4)
# 삭제
	heapq.heappop(heap)
# 최솟값 확인
	heap[0]
# 기존 리스트를 최소힙으로 변환
	heapq.heapify(heap)
# 힙 삽입시 음수로 넣으면 최대힙 구현가능

 

 

---

문제풀이

✅ 1620번 나는야 포켓몬 마스터 이다솜 (S4)

1620번: 나는야 포켓몬 마스터 이다솜

def getInput():
    n, m = map(int, input().split())
    pokemons_int = {}
    pokemons_str = {}
    for i in range(n):
        string = input()
        pokemons_int[str(i + 1)] = string
        pokemons_str[string] = str(i + 1)
    questions = [input() for _ in range(m)]
    return pokemons_int, pokemons_str, questions

def solution():
    pokemons_int, pokemons_str, questions = getInput()
    for target in questions:
        if target.isdigit():
            print(pokemons_int[target])
            continue
        print(pokemons_str[target])


solution()

 

✅ 14425번 문자열 집합 (S3)

14425번: 문자열 집합

def getInput():
    n, m = map(int, input().split())
    s = set()
    targets = []
    for _ in range(n):
        s.add(input())
    for _ in range(m):
        targets.append(input())
    return s, targets

def solution():
    result = 0
    s, targets = getInput()
    for target in targets:
        if target in s:
            result += 1
    return result


print(solution())

 

 

✅ 11279번 최대 힙 (S2)

11279번: 최대 힙

import sys
import heapq

def solution():
    n = int(sys.stdin.readline().rstrip())
    heap = []
    for i in range(n):
        x = int(sys.stdin.readline().rstrip())
        if x == 0:
            if not heap:
                print(0)
                continue
            print(-heap[0])
            heapq.heappop(heap)
        elif x > 0:
            heapq.heappush(heap, -x)  # maxHeap 형태


solution()

 

 

✅ 2075번 N번째 큰 수 (S2)

* 크기의 대소를 비교해 힙의 사이즈를 줄여보자

2075번: N번째 큰 수

import heapq

# 메모리 초과 관리
# "모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다" 조건을 활용해 메모리를 줄여보자
def solution():
    heap = []
    n = int(input())
    for _ in range(n):
        for num in list(map(int, input().split())):
            if len(heap) < n:
                heapq.heappush(heap, num)
                continue
            if num < heap[0]:
                continue
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    return heap[0]


print(solution())

 

 

✅ 4358번 생태학 (S2)

4358번: 생태학

import sys

def getInput():
    d = {}
    total = 0
    while True:
        key = sys.stdin.readline().rstrip()
        if key == '':
            break
        if key not in d:
            d[key] = 1
        else:
            d[key] += 1
        total += 1
    return d, total

def solution():
    d, total = getInput()
    sorted_d = sorted(d.items())
    for key, value in sorted_d:
        print(f'{key} {value / total * 100:.4f}')


solution()

 

 

✅ 11286번 절댓값 힙 (S1)

* 양수와 음수 케이스를 나눠서 계산 

* 정보를 참고할 수 있는 또 다른 필드를 두는 것도 염두

11286번: 절댓값 힙

import sys
import heapq

def solution():
    n = int(sys.stdin.readline().rstrip())
    heap = []
    for i in range(n):
        x = int(sys.stdin.readline().rstrip())
        if x == 0:
            if not heap:
                print(0)
                continue
            if heap[0][1] == 'negative':
                print(-heap[0][0])
            else:
                print(heap[0][0])
            heapq.heappop(heap)
        elif x > 0:
            heapq.heappush(heap, [x, 'positive'])
        elif x < 0:
            heapq.heappush(heap, [-x, 'negative'])


solution()

 

 

 

✅ 7662번 이중 우선순위 큐 (G4)

* 메모리 초과 (미리 저장하지 말고 받아서 바로 사용하는 방식으로 해결)

* 시간 초과 (삭제된 요소들은 딕셔너리로 관리, 배열에서 삭제하는 방식은 시간에 적합하지 않았음. 딕셔너리로 O(1) 처리해야 시간 맞음)

* heappush 할 때 O(logn) 주의, 시간 복잡도 통과 

7662번: 이중 우선순위 큐

import sys
import heapq

def solution():
    t = int(sys.stdin.readline())  # 입력 테스트 케이스 수

    for _ in range(t):
        min_heap = []
        max_heap = []
        exist = {}  # 힙에 존재하는 요소의 개수를 저장하는 딕셔너리

        k = int(sys.stdin.readline())

        for _ in range(k):
            order, str_n = sys.stdin.readline().split()
            num = int(str_n)
            if order == 'I':  # 요소 삽입 연산
                heapq.heappush(min_heap, num)  # 최소 힙에 삽입
                heapq.heappush(max_heap, -num)  # 최대 힙에 삽입
                exist[num] = exist.get(num, 0) + 1  # 요소의 개수 증가
            elif order == 'D':  # 요소 삭제 연산
                if num == -1:  # 최솟값 삭제
                    while min_heap and exist.get(min_heap[0]) == 0:
                        heapq.heappop(min_heap)  # 이미 삭제된 요소를 힙에서 제거
                    if min_heap:  # 힙이 비어있지 않은 경우
                        val = heapq.heappop(min_heap)  # 힙에서 최솟값 제거
                        exist[val] -= 1  # 요소의 개수 감소
                elif num == 1:  # 최댓값 삭제
                    while max_heap and exist.get(-max_heap[0]) == 0:
                        heapq.heappop(max_heap)  # 이미 삭제된 요소를 힙에서 제거
                    if max_heap:  # 힙이 비어있지 않은 경우
                        val = -heapq.heappop(max_heap)  # 힙에서 최댓값 제거
                        exist[val] -= 1  # 요소의 개수 감소

        while min_heap and exist[min_heap[0]] == 0:
            heapq.heappop(min_heap)  # 이미 삭제된 요소를 힙에서 제거
        while max_heap and exist[-max_heap[0]] == 0:
            heapq.heappop(max_heap)  # 이미 삭제된 요소를 힙에서 제거

        if not min_heap:  # 힙이 비어있는 경우
            print('EMPTY')
        else:  # 힙에 요소가 존재하는 경우
            print(-heapq.heappop(max_heap), heapq.heappop(min_heap))  # 최댓값, 최솟값 출력


solution()

 

 

✅ 21939번 문제 추천 시스템 Version 1 (G4)

* 우선순위가 있을 경우 (여기에선 난이도 기준) 힙

21939번: 문제 추천 시스템 Version 1

import sys
import heapq

def add(p, l, min_h, max_h):
    heapq.heappush(min_h, (l, p))
    heapq.heappush(max_h, (-l, -p))

def solved(p, min_h, max_h):
    if p == min_h[0][1]:
        heapq.heappop(min_h)
    elif p == -max_h[0][1]:
        heapq.heappop(max_h)

def recommend(x, min_h, max_h):
    if x == -1:
        print(min_h[0][1])
    else:
        print(-max_h[0][1])

def solution():
    n = int(sys.stdin.readline().rstrip())
    max_heap = []
    min_heap = []

    for _ in range(n):
        p, l = map(int, sys.stdin.readline().rstrip().split())
        heapq.heappush(min_heap, (l, p))
        heapq.heappush(max_heap, (-l, -p))

    m = int(sys.stdin.readline().rstrip())
    for _ in range(m):
        arr = list(map(str, sys.stdin.readline().rstrip().split()))
        order = arr[0]

        if order == 'add':
            add(int(arr[1]), int(arr[2]), min_heap, max_heap)
        elif order == 'solved':
            solved(int(arr[1]), min_heap, max_heap)
        elif order == 'recommend':
            recommend(int(arr[1]), min_heap, max_heap)


solution()

 

 

✅ 2696번 중앙값 구하기 (G2)

2696번: 중앙값 구하기

def print_medians(medians):
    length = len(medians)
    repeat = length // 10
    print(length)
    for i in range(repeat):
        for j in range(10):
            print(medians[(10 * i) + j], end=" ")
    if length // 10 != 0:
        print()
    for j in range(length % 10):
        print(medians[(10 * repeat) + j], end=" ")


def solution():
    t = int(input())
    for _ in range(t):
        m = int(input())
        repeat = m // 10
        arr = []
        for _ in range(repeat):
            arr = arr + list(map(int, input().split()))
        arr = arr + list(map(int, input().split()))

        length = 0
        target = []
        medians = []
        for i in range(len(arr)):
            target.append(arr[i])
            target.sort()
            length += 1

            if i % 2 == 0:  # 홀수 번째 수라면 (인덱스가 짝수)
                medians.append(target[i // 2])

        print_medians(medians)


solution()

 

 

✅ 21942번 부품 대여장 (G2)

21942번: 부품 대여장

def getInput():
    N, L, F = list(map(str, input().split()))
    info = [input() for _ in range(int(N))]
    return N, L, F, info

# 시간을 직렬화하자
def parsingDate(string):
    day, time = string.split('/')
    day = int(day)
    h, m = time.split(':')
    due_time = 24 * 60 * day + 60 * int(h) + int(m)
    return due_time

def parsingLog(string):
    # 2021년도는 2월이 28일까지
    months = {1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31}
    days = [0]
    for month, day in months.items():
        days.append(days[month - 1] + day)  # 누적합
    date, time, item, person = string.split()
    _, month, day = map(int, date.split('-'))
    hour, minute = map(int, time.split(':'))
    calculated_time = 24 * 60 * (days[month - 1] + day) + 60 * hour + minute
    return calculated_time, item, person

def solution():
    d = {}  # 빌린 물품에 대한 로그 추적을 위한 딕셔너리
    result = {}  # 벌금을 위한 딕셔너리

    N, L, F, info = getInput()
    due_time = parsingDate(L)

    for log in info:
        curr_time, item, person = parsingLog(log)

        if person not in d:
            d[person] = {}

        # d[person]에 이미 있으면, 반납해야 할 물건 이라는 뜻이다.
        # 벌금이 있으면 계산하고, d[person]에서 해당 아이템을 삭제한다.
        if item in d[person]:
            borrow_time = d[person].pop(item)  # 키로 꺼내기
            delay = (curr_time - borrow_time) - due_time
            if delay > 0:
                if person not in result:
                    result[person] = 0
                result[person] += delay * int(F)
        else:
            d[person][item] = curr_time  # 없다면, 빌리는 과정임

    # 사전 순으로 출력하기
    if result:
        result = sorted(result.items(), key=lambda x: x[0])
        for person, fine in result:
            print(f'{person} {fine}')
    else:
        print(-1)


solution()