나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42579 🔑 딕셔너리, 힙 music 딕셔너리 "장르" : [(-재생 횟수, 고유 번호), (-재생 횟수, 고유 번호)] value의 리스트는 힙이고 재생 횟수를 음수값으로 넣어 최대 힙 구현 play 딕셔너리 "장르" : 총 재생 횟수 앨범에 먼저 수록할 장르를 구하기 위한 딕셔너리 play 딕셔너리를 총 재생 횟수 기준으로 정렬 1번 조건 : 노래가 많이 재생된 장르를 먼저 수록합니다. 정렬한 play 리스트에서 pop() 2번 조건 : 장르 내에서 많이 재생된 노래를 먼저 수록합니다. music["장르"]에서 heappop() 장르 내에 속한 곡이 1개 일 때 처리를 try-except..

문제 : https://www.acmicpc.net/problem/1202 🔑 힙, 우선순위 큐 1. 입력받은 보석들을 무게 기준 오름차순 정렬 2. 가방도 오름차순 정렬 3. 가장 작은 가방부터 시작해서 이 가방에 담을 수 있는 보석이면 힙에 보석 가격을 담는다. (음수로 담는다. 최대힙) 4. 담긴 보석이 있으면 가장 비싼 보석을 선택한다. 3, 4번 과정을 가방 개수만큼 반복한다. 크기가 작은 가방부터 담기 때문에 보석을 모두 담고 뽑아내는 게 가능하게 된다. 크기가 2인 가방에 담을 수 있는 보석이면 크기가 3인 가방에도 담을 수 있다. 가방 크기 = [2, 10] 보석 = [(1, 65), (2, 99), (5, 23)] 가방 크기 2일 때 힙 = [-99, -65] -99를 뽑아서 정답으로 올..

문제 : https://www.acmicpc.net/problem/1715 🔑 최소 힙 힙에서 가장 작은 수 두 개를 뽑는다. heappop 두 번 뽑아낸 두 수를 더해서 힙에 다시 넣고 합한 값만큼 정답을 올려준다. from heapq import heappop, heappush import sys input = sys.stdin.readline n = int(input()) heap = [] for _ in range(n): heappush(heap, int(input())) answer = 0 while len(heap) >= 2: x = heappop(heap) + heappop(heap) heappush(heap, x) answer += x print(answer)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12927 🔑 최대 힙 works의 값들을 최대 힙으로 만든다. 최대 힙은 가장 큰 값이 가장 왼쪽에 있도록 한다. 최대 힙으로 만들려면 값들을 음수로 변경해서 힙에 추가하면 된다. works = [2, 4, 3] 일 때 이 값들을 음수로 바꿔서 힙에 넣으면 (heappush) [-4, -3, -2] 이렇게 가장 큰 값이 왼쪽에 있을 수 있다. heappop을 사용해서 가장 왼쪽 값을 빼낸 다음 1시간 작업한다. 4는 3이 돼야 하는데 현재 값은 -4로 되어있기 때문에 +1을 했다. 1시간 작업을 하고 빼낸 작업을 다시 힙에 넣는다. 이 작업을 n번 반복 후 야근 지수를 구하면 끝 ✨ from..

문제 : https://www.acmicpc.net/problem/21939 🔑 최소 힙, 최대 힙 사용 가장 어려운 문제 추천하기 위한 최대 힙 가장 쉬운 문제 추천하기 위한 최소 힙 💡 solved 명령이 들어오면 바로 빼지 않음 solved 1000 명령이라면 문제 리스트에서 1000을 찾고 빼야 하는데 이 과정이 시간 오래 걸림 그래서 solved한 문제는 따로 리스트에 보관하고 추천할 때 solved_list에 있으면 heappop 하는 방식 사용 같은 문제 번호에 다른 난이도가 새로 들어올 수 있으니까 solved_list에는 (문제 번호, 난이도)를 같이 저장해야 함 이때 해당 문제 번호의 난이도를 찾기 위해 딕셔너리를 사용 {문제번호 : 난이도} from heapq import heappo..

문제 : https://www.acmicpc.net/problem/1655 🔑 최대 힙과 최소 힙을 함께 사용 import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) num = int(input()) print(num) minHeap, maxHeap = [],[-num] for i in range(n-1): num = int(input()) if num > -maxHeap[0]: heappush(minHeap, num) else: heappush(maxHeap, -num) if len(minHeap) > len(maxHeap): temp = heappop(minHeap) heappush(maxHea..

문제 : https://www.acmicpc.net/problem/11000 그리디, 정렬, 우선 순위 큐 import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) lst = [list(map(int, input().split())) for _ in range(n)] # s에 시작 t에 끝나는 수업 [s, t] lst.sort() # 수업 시작 시간으로 정렬 room = [] heappush(room, lst[0][1]) # 첫 강의 끝 시간 for i in range(1, n): if lst[i][0] < room[0]: # 다음 수업 시작 시간이 현재 수업 종료 시간보다 작으면 (강의 중이면) h..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42628 힙(heap) 🔑 최솟값 제거는 heappop()을 사용 🔑 최댓값 제거를 위해 pop()을 했으나 힙 자료구조는 모든 원소를 정렬하지 않기 때문에 마지막 값이 최댓값이라는 보장이 없다. 🔑 그래서 최댓값을 구할 때는 sort()로 새롭게 정렬을 해주고 pop()을 했다. (정답 리턴 때도 마찬가지) from heapq import * def solution(operations): heap = [] for i in operations: if i[0] == "I": heappush(heap, int(i[2:])) # 숫자 부분만 슬라이싱, 형 변환 후 힙에 추가 elif i == "D..