[백준] 1874.cpp 스택 수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

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

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n = 0;
  cin >> n;
  int data = 0;

  // 입력받는 수들을 차례대로 저장해 둔다.
  vector<int> v;
  v.reserve(n);
  for(int i = 0 ; i < n ; i++)
  {
    cin >> data;
    v.emplace_back(data);
  }

  // 1부터 시작해서 다른 벡터(스택역할)에 하나씩 넣으면서 위의 수열과 비교
  int i = 0; // 위의 수열에 대한 인덱스값
  int next = 1; // 스택에 넣을 다음 원소값
  int cur = -1; // 스택이 현재 가리키고 있는 위치
  vector<int> vstack;
  string ans = ""; // 출력용 답
  while(i < n) // 기준 수열을 다 돌 때 까지
  {
    if(next > n) // 만약 다 돌았는데 안끝났으면 답은 NO 이므로 빠져나간다.
    {
      ans = "NO";
      break;
    }
    vstack.push_back(next++); // 스택에 현재 원소값을 넣고
    cur++; // 스택 현재 인덱스
    ans += "+\n"; // 푸시 했으니 + 하나 추가
    while(vstack[cur] == v[i] && v[i] != 0) // 현재 스택 인덱스와 기준 수열의 인덱스 비교
    {
      vstack.pop_back(); // 같을 경우 하나 뺴주고
      cur--; // 스택에서 하나 뺐으니 감소
      i++; // 하나 일치했으니 기준 수열 인덱스는 다음 값으로
      ans += "-\n"; // - 하나 추가
    }
  }
  cout << ans;
}

 

[Try]

1. 수열을 두개 만들어서 비교해가면서 답을 뽑아냈다.

 

[Point]

1. 애초에 기준 수열을 입력 받을 때부터 스택에 푸시, 팝을 통해 비교할 수 있었다. 입력받은 값이 현재 저장해야 할 값보다 크다면

     스택에 전부 넣고, 스택 맨 위의 값을 비교해서 하나씩 뺴주는 방식이다. 진짜 효율적인 것 같다. (6170888)

2. 앗 근데 비슷하게 푸신 분들이 좀 있다. 나만 미련하게 푼듯

3. 뽑을 값이 내림차순으로 있어야 스택에서 정상적으로 pop 할 수 있다는 성질을 잘 이용해야 할 것 같다.

 

[More]

1. for(auto i : v) 형식의 반복문, auto 자료형