1874번

수도 코드

N (수열 개수)
A (수열 저장 배열)
S (스택)
answer (결과 저장)

N입력
for(N만큼 반복):
	A에 데이터 저장

for(N만큼 반복):
	if(A에 현재 수열 값 >= 오름차순 자연수):
    	while(값이 같아질때 까지):
    		S.push(자연수)
            answer += "+" // (+) 저장
        S.pop()
        answer += "-" // (-) 저장
        
	else:
    	top = S.pop()
        if(top이 현재 수열값이 아니라면):
        	NO 출력
            프로그램 종료
        else:
        	answer += "-" // (-) 저장
         
for(answer.length()만큼 반복):
	answer[i] 출력

답안

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int N, number;
vector<char> answer;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
  
  cin >> N;
  
  vector<int> A(N, 0);
  stack<int> S;
  number = 1;

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

  for(int i = 0; i < N; i++){
    if(number <= A[i]){
      while(number <= A[i]){
        S.push(number++);
        answer.push_back('+');
      }
      S.pop();
      answer.push_back('-');
    }
    else{
      int result = S.top();
      S.pop();
      if(result != A[i]){
        cout << "NO" << "\n";
        exit(0);
      }
      else{
        answer.push_back('-');
      }
    }
  }
  for(int i = 0; i < answer.size(); i++){
    cout << answer[i] << "\n";
  }
}

17298번

수도 코드

아이디어

• 스택에 들어오는 수에는 인덱스와 값이 필요하다.
• 스택에 새로 들어오는 수가 top의 값보다 크면 그 수는 top의 인덱스의 오큰수가 된다.

N (수열 개수), A(수열의 현재 수) , answer(정답 배열)
pair<인덱스, 값> Node (스택에 들어가는 노드)
stack<Node> myStack (스택)

answer 배열을 -1로 초기화
myStack 선언

for(N만큼 반복):
	A 입력 받기
	while(!myStack.empty() && 스택의 top의 값보다 A의 값이 크다면):
    	top Node 인덱스의 오큰수는 A이다
        스택을 pop한다. 
    
    A를 Node로 만들어 스택에 push한다.

answer 배열 출력

답안

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
typedef pair<int, int> Node;

int N, A;

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

  cin >> N;
  vector<int> resultV(N, -1);
  stack<Node> myStack;

  for (int i = 0; i < N; i++) {
    cin >> A;
    while (!myStack.empty() && myStack.top().second < A) {
      resultV[myStack.top().first] = A;
      myStack.pop();
    }
    myStack.push(Node(i, A));
  }

  for (int i = 0; i < N; i++) {
    cout << resultV[i] << " ";
  }
}

팁

• 1:1 매칭이 되지만 반복문을 사용하기엔 시간복잡도가 클 때 스택을 생각해보자
• 스택의 동작을 상상할 때 골목길에 작은 사람, 큰 사람이 들어오는 듯한 상황을 떠올려 보자.

2164번

수도 코드

N (카드 개수)
myQueue(카드 저장 큐)

for(N만큼 반복):
	큐에 카드 저장
    
while(카드가 1장 남을 때까지):
	맨 위의 카드를 버린다
    맨 위의 카드를 제일 아래로 이동시킨다.

마지막으로 남은 카드 출력

답안

#include <bits/stdc++.h>
using namespace std;

int n;
deque<int> dq;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		dq.push_back(i);
	}
	while (dq.size() != 1) {
		dq.pop_front();
		int temp = dq.front();
		dq.pop_front();
		dq.push_back(temp);
	}
	cout << dq.front();
	return 0;
}

11286번

아이디어

• 우선순위 큐에 정렬 기준을 새로 적용하기

수도 코드

N (질의 요청 개수)
myQueue(데이터 저장 우선순위 큐)
절대값 기준으로 정렬되도록 설정.
단, 절대값이 같다면 음수 우선 정렬

for(N만큼 반복):
	요청이 0일 때: 큐가 비었으면 0출력, 아니면 큐의 top 출력하고 pop
    요청이 1일 때: 새로운 데이터를 우선순위 큐에 push

답안

#include <iostream>
#include <queue>

using namespace std;

int queryN;

struct compare{
  bool operator()(int o1, int o2){
    if(abs(o1) == abs(o2)) return o1 > o2;
    return abs(o1) > abs(o2);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> queryN;
  priority_queue<int, vector<int>, compare> myQueue;

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

연산자 오버로딩

struct compare{
  bool operator()(int o1, int o2){
    return o1 > o2;
  }
};

int main() {
  priority_queue<int, vector<int>, compare> myQueue;
}

우선순위 큐에는 top 개념이 있다.
pop을 하면 이 top 이 빠져나오고 push를 하면 top에서 제일 먼 쪽 노드와 비교하여 자리를 찾아간다.

비교 연산자를 오버로딩한 위의 함수에 o1 매개변수에는 top에서 제일 먼 쪽 노드가 들어가고 o2 매개변수에는 현재 노드가 들어간다.
리턴값이 true일 땐 swap이 일어나고 false일땐 일어나지 않는다.

즉, 위에서는 현재 노드가 앞의 노드보다 작다면 swap해라는 의미이다.
큐에 있는 어느 값보다도 제일 작은 값이라면 이 값은 top까지 swap될 것이다.