< 백준 BaekJoon : 12789번 도키도키 간식드리미> C++

<< 문제 >>

https://www.acmicpc.net/problem/12789

12789번: 도키도키 간식드리미

 

다른 방법이 있을 수 있지만 두 개의 스택을 활용해 문제를 해결했다.

 

1. 첫 번째 stack 확인

    가장 앞에 선 사람이 지금 받을 번호가 맞다면 ->  stack에서 pop하고 다음 번호 찾기

    가장 앞에 선 사람이 지금 받을 번호가 아니라면 -> 두 번째 Stack을 확인

2. 두 번째 stack 확인

    top에 있는 사람이 지금 받을 번호가 맞다면 ->  stack에서 pop하고 다음 번호 찾기

    top에 있는 사람이 지금 받을 번호가 아니라면 -> 첫 stack의 top을 두 번째 stack으로 push

 

 

이 과정을 다 거친 후에 첫 스택이 비었다면 완성되거나 두 번째 스택에 남은 사람이 있을 것. 

 

두 번째 스택에서는 순서대로 서 있어야 모두 간식을 받을 수 있고, 하나라도 순서가 잘못되면 안 됨.

 

그래서 top부터 꺼내보며 다음 순서와 맞다면 넘기고, 다르면 바로 false를 return 한다. 

 

 

<< 코드 >>

 

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// stack 거꾸로 만드는 함수
void stackInversing(stack<int>& st){
  stack<int> temp;

  while(!st.empty()){
    temp.push(st.top());
    st.pop();
  }

  st.swap(temp);
}

// 간식 받을 수 있는지 확인하는 함수
bool isValid(stack<int> st1) {
  stackInversing(st1); // 동작 위해 st1을 뒤집어줌
  
  stack<int> st2;
  
  int currentNum = 1;
  // st1을 비우는 과정
  while (!st1.empty()) {
    if (st1.top() == currentNum) {
      st1.pop();
      currentNum++;
    } 
    else if (!st2.empty() && st2.top() == currentNum) {
      st2.pop();
      currentNum++;
    } 
    else {
      st2.push(st1.top());
      st1.pop();
    }
  }
  
  // st2는 순서대로 있어야 함
  while(!st2.empty()){
    if(st2.top() == currentNum){
      st2.pop();
      currentNum++;
    }
    else{
      return false;
    }
  }
  
  return true;
}

int main() {
  int num;
  cin >> num;

  stack<int> st;

  for (int i = 0; i < num; i++) {
    int input;
    cin >> input;
    st.push(input);
  }


  
  if(isValid(st)){
    cout << "Nice" << '\n';
  }
  else{
    cout << "Sad" << '\n';
  }
}