[백준 25556번] 포스택 (C++)

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

25556번: 포스택

문제가 스택을 이용해야할거 같지만 풀이과정에서 굳이 스택이 필요한가 싶다.

(물론 스택 자료구조에 대한 이해는 필요하다)4개의 스택이 있다고 했으니 크기가 4인 벡터를 만들어서 각각 스택의 최상위 값만 벡터에 담는 식으로 하여 스택없이 문제를 해결하였다.Greedy한 문제인데 풀이는 별로 어렵지 않다. 순열에서 숫자를 하나씩 꺼내서 벡터에 넣는데, 4개의 스택이라고 정해놓은 곳의 숫자보다 큰 값만 들어와야지 다시 일렬로 낼 수 있다.그 뜻은 순열이 숫자가 감소하는 부분이 5번 이상 나오면 스택에 넣을 자리가 없다는 뜻이다.근데 여기서 주의해야할 점은 가장 차이가 최소인 스택에 숫자를 넣어야하므로 숫자를 넣을때마다 차이가 가장 작은 벡터인덱스(스택)에 넣어주어야한다.코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#define endl "\n"

using namespace std;
int main(){
  int n, min, min_idx;
  cin >> n;
  vector<int> seq(n);
  for(int i = 0; i < n; i++){
    cin >> seq[i];
  }
  vector<int> stack(4);
  vector<int> diff(4);
  for(int i = 0; i < n; i++){
    int tmp = seq[i];
    bool check = false;
    min = 100001;
    min_idx = 100001;
    for(int j = 0; j < 4; j++){
      diff[j] = tmp - stack[j];
      if(min > diff[j] && diff[j] > 0){
        min = diff[j];
        min_idx = j;
        check = true;
      }
    }
    if(check) stack[min_idx] = tmp;
    else{
      cout << "NO";
      return 0;
    }
  }
  cout << "YES";
}