Tori의 개발 공부

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42628🛠 문제 상황프로그래머스에서 해당 문제를 풀기 위해서는 최댓값과 최솟값을 모두 O(1)로 조회하면서도 O(log N)으로 삽입/삭제가 가능한 자료구조가 필요했습니다.기존의 단일 우선순위 큐(Heap)만으로는 한쪽 방향의 정렬만 유지할 수 있어, 최댓값과 최솟값을 동시에 효율적으로 관리할 수 없었습니다.✅ 해결 방법최대 힙(Max Heap)과 최소 힙(Min Heap)을 동시에 유지하는 Dual Heap을 구현했습니다. 이중 우선순위 큐는 두 개의 힙을 사용하여 최댓값과 최솟값을 빠르게 찾을 수 있도록 합니다.📌 핵심 아이디어최소 힙(minHeap): 최솟값을 빠르게 조회하기 위한 ..

Heap 이란? 데이터에서 최댓값 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리로 우선순위 큐를 위해 만들어진 자료구조 최대힙(max heap) : 부모노드 ≥ 자식노드 최소힙(min heap) : 부모노드 ≤ 자식노드 💡 완전 이진 트리란? 이진트리 = 자식 노드가 최대 두 개인 트리 완전 이진트리 = 마지막 레벨을 제외한 모든 노드가 2개씩 채워져 있으며, 최하단 레벨 또한 좌측부터 채워져있는 노드를 의미한다. 즉 완전 이진트리는 왼쪽부터 자식 노드를 차례로 채운다. index 성질 heap은 완전 이진 트리 구조이기 때문에 노드 간 인덱스 관계를 나타낼 수 있다. → 완전 이진트리는 무조건 왼쪽부터 채워지기 때문에 채워지는 순서가 있음 = index 부모 노드 index = 자식 노드 index ..

문제 파이썬 풀이 from collections import Counter def solution(k, tangerine): cnt = Counter(tangerine) answer = 0 box = 0 for i in cnt.most_common() : box += i[1] answer += 1 if box >= k : break return answer Counter 클래스를 사용하여 문제를 해결하였다. 우선 Counter클래스를 통해 크기 별로 몇 개의 귤을 가지고 있는지 계산을 한다. Counter클래스의 most_common() 메서드를 통해 귤 개수를 내림차순으로 정리한 리스트를 반복문으로 돌며 가장 많은 개수를 가진 귤부터 box에 넣어준다. (box변수는 현재 box안에 들어 있는 귤의 개..

문제 파이썬 풀이 def solution(k, score): answer = [] scoreList = [] for i in score : scoreList.append(i) scoreList.sort() if len(scoreList) < k : answer.append(scoreList[0]) else : answer.append(scoreList[-k]) return answer score변수에서 하나씩 꺼내어 리스트에 차례로 담고 오름차순 정렬을 진행한다. 그리고 초기 k일이 지나기 전에는 모든 사람들이 명예의 전당에 오르게 되므로 가장 점수가 작은 0번째 인덱스 값을 answer리스트에 추가한다. k일 이후부터는 뒤에서 k번째 점수가 명예의 전당 마지막 점수이므로 -k번째 인덱스 값을 추가해준다.