문제 자체는 이해하기 쉬웠지만 어느 자료구조를 선택해야지 베스트인지는 바로 떠오르지 않았다. 왜냐하면 가장 작은 값을 출력도 해야하고 출력후 가장 작은 값을 제거도 해야하기 떄문이다.

나는 vector를 사용해서 시작 했는데 시간초과가 나 버렸다...

오답 코드

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
vector<int> ret;

void solve(){
    int minVal = *min_element(v.begin(),v.end()); // 최소값 찾기
    ret.push_back(minVal); // 최소값 ret 벡터에 넣어주기
    v.erase(min_element(v.begin(),v.end())); // 최소값 삭제
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        if(tmp == 0) {
            if(v.size() == 0) {
                ret.push_back(0);
            }
            else {
                solve();
            }
        }
        else {
            v.push_back(tmp);
        }
    }

    for(auto it : ret) cout << it << "\n";
    return 0;   
}

IDE에선 정답이라고 뜨는데 시간초과로 오답처리가 된 케이스이다.
이유는 min_element 함수를 사용하여 최소값을 찾으므로 O(N)의 시간이 소요되고. 제거 연산 역시 최소값을 찾기 위해 O(N)의 시간이 소요되므로, 총 O(N)의 시간이 소요된다.
따라서, N개의 연산을 수행하는 경우 전체 시간 복잡도는 O(N^2)이다.

마땅한 자료구조가 떠오르지 않아서 벡터로 사용한거 인데... 라이브러리에 익숙해져서 함수 호출을 하려 해결하려고 보니 시간복잡도 부분은 효율이 좋지 않았다.

수정 코드

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> n;
  for(int i = 0; i < n; i++){
      int tmp;
      cin >> tmp;
      if(tmp == 0) {
          if(pq.empty()){
              cout << 0 << "\n";
          }
          else {
              cout << pq.top() << "\n"; 
              pq.pop();
          }
      }
      else {
          pq.push(tmp);
      }
  }

  return 0;   
}

우선순위큐가 heap자료구조 사용해서 만들어진걸 기억을 해서 한 번 검색을 해봤다... 왜냐하면 큐만 써봤지 우선순위큐의 대해선 많이 잘 모르기 떄문이였다.

기본적으로 C++에서 자주 쓰이는 vector와 같은 container adaptor의 한 종류이며 C++에서 int와 같은 기본자료형으로 우선순위 큐를 사용한다면 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다

우선순위 큐는 데이터의 삽입 및 삭제에 대한 시간 복잡도가 O(logN)으로 벡터의 삭제인 O(N)의 비해 효율적이다.

기본 선언은

priority_queue pq; == priority_queue<int, vector, less> pq;

나는 오름차순으로 출력을 해야하니 아래와 같이 선언을 해줘여했다.

  priority_queue<int, vector<int>, greater<int>> pq;

      if(tmp == 0) {
          if(pq.empty()){
              cout << 0 << "\n";
          }
          else {
              cout << pq.top() << "\n"; 
              pq.pop();
          }
      }
      else {
          pq.push(tmp);
      }

만약에 0을 입력받고 우선순위 큐가 비어 있으면 0을 출력하고 비어 있지 않으면 가장 작은 수를 출력을 해주고 즉 우선순위큐의 top() 부분이다. 그러고 나선 우선순위큐를 pop()해준다.

그리고 0이 아닌 다른 값을 입력을 받으면 우선순위 큐에 넣어준다.

우선순위큐의 유형

1. 최소 혹은 최대 값 관리: 우선순위 큐는 내부적으로 최소 힙 혹은 최대 힙을 사용하여 가장 작은 혹은 가장 큰 값을 빠르게 찾을 수 있습니다. 따라서, 최소 혹은 최대 값을 유지하거나 필요한 값을 찾는 문제에서 활용될 수 있다.
2. 이벤트 시뮬레이션: 일련의 이벤트를 시뮬레이션하거나 처리해야 하는 경우, 우선순위 큐를 사용하여 다음에 처리해야 할 이벤트를 선택하는 방식으로 문제를 해결할 수 있다. 예를 들어, 시간 순서에 따라 다양한 이벤트가 발생하고, 이벤트를 처리해야 할 때 우선순위 큐를 사용하여 다음 처리할 이벤트를 선택할 수 있습니다.
3. 그래프 알고리즘: 우선순위 큐를 사용하여 그래프 알고리즘에서 최단 경로 문제나 최소 스패닝 트리(MST) 등을 해결할 수 있다. 다익스트라 알고리즘과 프림 알고리즘이 대표적인 예시.
4. 스케줄링: 작업이나 이벤트의 우선순위에 따라 스케줄링을 수행해야 하는 경우, 우선순위 큐를 사용하여 작업을 관리하고 처리할 수 있다.