https://leetcode.com/problems/seat-reservation-manager/
heap
1. 문제 및 접근
1845. Seat Reservation Manager
3개의 메서드
1. SeatManager(int n)의 자리 초기화
2. reserve 예약하면 작은 수부터 예약하고, 작은 수 반환
3. unreserve 들어온 자석 번호 취소 void
O(n)으로 푸니 마지막에 시간초과 걸림
Constraints:
- 1 <= n <= 10^5
- 1 <= seatNumber <= n
- For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
- For each call to unreserve, it is guaranteed that seatNumber will be reserved.
- At most 105 calls in total will be made to reserve and unreserve.
2. 첫 풀이
public class SeatManager {
int n;
private int[] seat;
public static void main(String[] args) {
int n = 5;
SeatManager main = new SeatManager(n);
}
public SeatManager(int n) {
this.n = n;
seat = new int[n + 1];
}
public int reserve() {
for (int i = 1; i <= n; i++) {
if (seat[i] == 0) {
seat[i] = i;
return i;
}
}
return n;
}
public void unreserve(int seatNumber) {
seat[seatNumber] = 0;
}
1. SeatManager(int n)
초기화 시 배열의 크기만큼 0의 기본 값을 가진 배열 생성
2.reserve()
reserve()배열이 숫자를 가지고 있지 않으면 그 자리에 작은 수부터 숫자를 채워준다.
즉 예약이 되지 않았다면 (초기화 상태는 0의 값) 예약 시 앞에서부터 채움
3.unReserve()
들어온 좌석 번호를 0(초기값)으로 설정해준다.
실패 이유 ?
reserve()는 최대 10^5만큼 호출이 가능하다.
n의 최대 값은 = 10^5
reserve()의 호출 최대 횟수는 10^5
O(n * 10^5)
10^10 = 10,000,000,000 최대 백억 번의 연산을 해야해서
그렇다면 O(n)의 시간 복잡도보다 더 효율적인 방법을 써야 한다.
3. heap
전에도 heap만 간단히 사용한 적이 있다
궁금하면 대충 보고오자
99클럽 코테 스터디 31일차 TIL Sort Characters By Frequency feat. Comparator vs Comparable
99클럽 코테 스터디 31일차 TIL Sort Characters By Frequency feat. Comparator vs Comparable
https://leetcode.com/problems/sort-characters-by-frequency/submissions/1293844763/ getOrDefualtpriorityQueuemaxHeapmapEntry 1. 문제 및 접근 주어진 s를 나타나는 빈도수에 대해 내림차순으로 반환같은 수의 빈도라
ernest45.tistory.com
힙(heap)이란 ?
- 완전 이진 트리(Complete Binary Tree) 형태
간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
- 각 노드의 값이 자식 노드들의 값보다 작거나 큰 특정한 조건을 만족하는 자료 구조.
- 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
- 배열 기반으로 구현
힙은 다익스트라 알고리즘(Dijkstra's algorithm)과 같은 최단 경로 알고리즘, 힙 정렬(Heap Sort) 등에서 사용.
특히 데이터의 동적인 삽입 및 삭제가 빈번한 상황에서 우수한 성능을 가짐
- 최대값 또는 최솟값 검색: 최대 힙에서는 루트 노드에 최대값이 위치하며, 최소 힙에서는 루트 노드에 최소값이 위치하므로 이를 O(1) 시간에 가져올 수 있음
- heap의 경우 추가와 삭제의 경우O(log n)가 걸린다. 자식과 비교해서 작거나 클 경우 위치를 교환하고, 트리의 레벨에 비례
힙은 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용
우선순위 큐란?
- 큐는 FIFO 형식의 자료구조
- 우선순위 큐는 큐에 우선순위라는 개념을 접목시킨 자료구조이다.
- 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
최대 값이 root 값이 되는 maxheap
최소 값이 root 값이 되는 minheap 의 종류가 있다
힙에서의 부모 노드와 자식 노드의 관계
- 부모의 인덱스 = (자식의 인덱스) / 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
4. heap을 이용한 풀이
public SeatManagerHeap(int n) {
this.n = n;
minHeap = new PriorityQueue<>();
for (int i = 1; i <= n; i++) {
minHeap.add(i);
}
}
public int reserve() {
int q =minHeap.remove();
System.out.println(q);
return q;
}
public void unreserve(int seatNumber) {
minHeap.add(seatNumber);
}
풀이 자체는 너무 간단하다.
4-1. SeatManager(int n)
n명 예약자가 들어오면
그 수에 맞춰서 heap의 기본 값인 minheap을 우선순위 큐로 구현
1부터 오름차순으로 넣어줌
4-2. reserve()
minHeap에서 우선순위에 의한 작은 수 부터 삭제
예약이 된다면, 있는 heap에서 빼준다.
4-3. unReserve(int seatNum)
다시 heap에다가 들어온 좌석 번호를 추가
예약을 취소하면 heap에다 추가해준다.
4. 마무리
왜 heap으로 사용했는가?
첫 풀이에서는 O(n)으로 시간 복잡도에서 걸렸다. 그러나 heap의 경우 추가와 삭제의 경우 O(log n)가 걸린다.
루트의 요소와 자식 노드들을 비교하여 작으면 위치를 바꾸고, 트리의 높이에 비례하기 때문에 O(log n)
root에 접근하는 것은 O(1)의 시간 복잡도를 가지기에 O(n)보다 훨씬 유리하기 때문이다.
이 문제는 시간 복잡도에 대해 이해할 수 있고, O(n)보다 더 효율적으로 관리하는 자료 구조를 알고 있는 지 묻는 문제인 것 같다.
바로 heap으로 떠올리진 않았지만, 잘 생각해보면 O(10^5 * 10^5)라는 걸 알 수 있었을텐데.. 너무 성급하게 풀었네
따로 어렵진 않은데 얼마나 잘 이해하고 있는 지 여부를 묻는 게 핵심이다.
'알고리즘' 카테고리의 다른 글
| 99클럽 코테 스터디 40일차 TIL Optimal Partition of String (0) | 2024.06.28 |
|---|---|
| 99클럽 코테 스터디 39일차 TIL Reduce Array Size to The Half (0) | 2024.06.27 |
| 99클럽 코테 스터디 36일차 TIL Removing Stars From a String (0) | 2024.06.24 |
| 99클럽 코테 스터디 35일차 TIL Flatten Nested List Iterator (0) | 2024.06.24 |
| 99클럽 코테 스터디 34일차 TIL Find the Winner of the Circular Game (0) | 2024.06.23 |