[우선순위 큐] N번째 큰 수 - 백준 2075번

1 분 소요

수많은 메모리 초과와 시간 초과를 경험,,
메모리와 시간 최적화 개선을 볼 수 있음

시행착오

모든 수를 list에 넣어서 정렬한다 -> 5번째로 큰 숫자를 찾는다!
메모리 제한 (12MB)
- $N ≤ 1500$ ⇒ 1500 * 1500 = 2,250,000 int 배열
- int : 4 byte ⇒ 2,250,000 * 4 = 9,000,000 byte => 9MB < 12MB (부합)
- 정렬 == NlogN

vector<int> vec(N*N);

for(int i=0;i<N;i++) {
    for(int j=0;j<N;j++) {
        int val;
        cin >> val;
        vec.push_back(val);
    }
}

vec 벡터가 N*N 크기만큼 할당해준 상태에서 push_back() 메서드로 값을 추가하는 멍청한 짓
- 크기가 이미 할당되어 있는 상태에서 push_back()을 하게되면 할당된 공간 맨 뒤에 값을 넣음
- 그니까 N*N+1 부터 N*N+N*N 까지 값이 들어감
- 결국 0 부터 N*N+N*N 까지 총 2N*N 메모리를 사용 ⇒ 18MB 사용

그래 그럼 할당을 해주지 말자, 그리고 push_back()

vector<int> vec;

for(int i=0;i<N;i++) {
    for(int j=0;j<N;j++) {
        int val;
        cin >> val;
        vec.push_back(val);
    }
}

vector<int> vec(N*N);

for(int i=0;i<N;i++) {
    for(int j=0;j<N;j++) {
        cin >> vec[i * N + j];           
    }
}

여기서 끝난 줄 알았건만,, 시간초과~~

이중 for문이라 1500 * 1500 이어도 될줄 알았는데 입력을 많이 받아서 시간 초과가 뜬 것 같다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);

“모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다.”

N번째로 큰 값 ⇒ 최소 힙

priority queue 선언
- min heap 최소 힙으로 선언한다. (N번째로 큰 값)
  - priority_queue<int, vector<int>, greater<int> > pq;
- max heap 최대 힙 (Default)
  - priority_queue<int> pq;
힙이 N개의 원소보다 작으면 그냥 추가
힙이 꽉 차고 새로운 값이 힙의 최소값보다 크면, 최소값을 제거하고 새로운 값을 추가
힙에는 5개의 가장 큰 수 Top 5가 오름차순으로 채워져 있음
그 중 제일 작은 수 min heap의 top을 출력

메모리 효율성: 항상 최대 N개의 값만 저장하므로, 메모리 사용을 O(N)으로 제한한다.
시간 복잡도: 삽입과 삭제는 각각 O(log N)의 시간 복잡도를 가진다. N*N개의 값을 순차적으로 처리할 때는 O(NN log N)이 된다. 이는 정렬을 사용한 O(NN log (NN))보다 효율적이다.