본문 바로가기

Heap4

[Leetcode] 703. Kth Largest Element in a Stream 문제 : https://leetcode.com/problems/kth-largest-element-in-a-stream/ k, nums 배열을 초기값으로 입력받고, 정수값 val을 nums 배열에 추가하는 함수 add를 제공할 때, k번째로 큰 원소를 찾기위한 클래스를 설계해라. 최대힙, 최소힙을 만들고 최소 힙의 크기는 k로 유지시킨다. 최소힙에는 k개의 큰 수들이 들어갈 것이고 이외의 수들은 모두 최대힙에 넣는다. nums = [1,2,7,4,3], k = 2 로 예를 들어보자. 1, 2 원소는 min heap에 용량이 아직 남았으므로 모두 min heap 에 넣어준다. 3번째 원소 7을 넣을때는 min heap이 모두 찼으므로 min heap의 top에 있는 수와 7을 비교한다. min heap의 .. 2022. 4. 8.
[Programmers] 디스크 컨트롤러 문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 먼저 시작시간이 가장 빠르고, 시작시간이 같다면 소요시간이 적은 순으로 jobs를 정렬한다. 마지막 작업이 종료된 시간(let, 종료시간)을 저장하는 변수를 하나 만들고 0으로 초기화시킨다. 가장 먼저 시작되는건 jobs의 첫번째 요소일 것이다. 작업 소요시간이 적은 순으로 정렬되는 최소힙을 하나만들어서 가장 먼저 시작되는 jobs의첫번째 요소를 큐에 넣는다. 이제 최소힙 빌때까지 잡들의 최소 소요시간을 구해서 sum 변수에 더해나간다. 최소힙의 첫번째 요소를 꺼내서 job의 실제 시작시간을 구한다. 만일 이전 잡의 종료시간이 현재 job의 시작시간보다 작거나 같으면 현재 job의 시작시간이 실.. 2021. 6. 11.
[leetcode][295] Find Median from Data Stream 문제 : https://leetcode.com/problems/find-median-from-data-stream/ 정렬된 배열의 중앙값을 찾아라. 만약 배열에 짝수개 있다면 중앙값 2개의 평균값을 구해라. addNum(num) num을 배열에 추가한다. findMedian() 배열의 중앙값을 구하라. 최소힙, 최대힙 으로 푸는 유명한 문제. 왼쪽에는 최대힙, 오른쪽에는 최소힙을 두고 addNum을 할 때 왼쪽 오른쪽 순으로 번갈아가며힙에 수를 넣어준다. 이 때, 왼쪽에 있는 최대힙 원소들은 오른쪽에 있는 최소힙에 있는 원소들보다 모두 작거나 같아야 한다. 따라서 addNum을 할 때 최소힙, 최대힙의 가장 위(앞)에 있는 수를 비교해서 최대힙에 있는 수가 최소힙에 있는 수보다 크다면 두 수를 바꿔서 넣.. 2020. 8. 17.
[leetcode][1329] Sort the Matrix Diagonally 문제 : https://leetcode.com/problems/sort-the-matrix-diagonally/ 입력으로 받은 배열의 대각선 요소들을 오름차순 정렬한 뒤 반환하는 문제 최소힙으로 풀었다. 대각선 요소들을 하나의 힙에 넣어야 한다. 인덱스 0 1 2 3 0 2 3 4 5 1 1 2 3 4 2 0 1 2 3 3x4 배열의 대각선 인덱스를 구하면 위와 같다. (구현에 따라 달라질 수 있음) 대각선 배열의 최대 크기는 n+m-1 이다. (m: 행, n: 열) mat[i][j]의 대각선 인덱스는 i+j-m-1 이다. 위 표를 보았을 때 열의 가장 아래부터 시작하기 때문에 m을 빼주었다. 1은 인덱스는 0부터 시작하기 때문에 뺐다. 따라서 n+m-1 개의 최소 힙을 배열에 저장한뒤, mat 배열을 .. 2020. 2. 15.

티스토리툴바