[백준 BOJ][stack] 1874 스택 수열

링크

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

1874번: 스택 수열

풀이

입력으로 주어진 n개의 숫자로 이루어진 수열을 스택의 push, pop 입출력으로 만들어낼 수 있는지와 그 과정을 알려주는 코드를 짜야합니다.

 

다음과 같은 과정을 반복하면 되는데요.

 

1. 1~n까지 반복문을 수행합니다.

2. 가장 먼저 push를 수행합니다.

3. 스택이 비어있지 않으면 수행하는 while 반복문을 넣어줍니다. 여기선 더 이상 '수열과 일치하는 pop을 할 수 없을 때까지' pop을 수행합니다.

 

아래가 핵심 코드입니다.

 

for (int i = 1; i <= n; i++) { // 입력은 오름차순으로 주어짐
    stk.push(i);                 // 오름차순으로 push
    result[rescount++] = '+';

    while (!stk.empty()) { // pop 할 수 있는 데까지 pop함
      if (arr[arrcount] == stk.top()) {
        stk.pop();
        arrcount++;
        result[rescount++] = '-';
        continue;
      }

      break; // pop 못하면 다음 push하러
    }
  }

 

만약 수열이 스택으로 만들 수 있는 정상적인 수열이라면, 마지막 n번째 반복을 수행할 때에는 while 반복문 안에서 모든 pop이 수행되고 스택이 비게 될 것입니다.

아니라면, n까지 최적을 지키며(매 반복마다 pop을 할 수 있을 만큼 계속 수행하며) 모두 push를 했지만 결국 뒷부분이 일치하지 않게 되어 스택에 숫자들이 남게 됩니다.

 

따라서 그리디처럼 계속해서 최선의 선택을 했을 때 마지막 결과가 성공적이라면 정상적인 수열이지만, 숫자가 남으면 이는 비정상적인 수열이라는 것입니다.

 

예제와 함께 살펴봅시다.

 

 

정상적인 수열의 예시입니다. 그림이 조금 복잡하긴 하지만 push를 수행하고, 왼쪽의 수열과 비교하면서 pop을 수행하고 하지 못할 경우 다음 push로 넘어가는 것을 확인할 수 있습니다.

그리고 마지막 8번째 반복을 보면 8, 7, 5, 2, 1 순서대로 수열과 일치해주면서 모든 값을 pop 하는 걸 확인할 수 있습니다.

 

비정상적인 수열의 예시입니다. 1, 2, 5까지는 정상적으로 pop 했지만 마지막 5번째 반복 때 스택에 모든 데이터들이 pop되지 않으면서 비정상적인 수열임을 알 수 있습니다.

 

마지막으로 정상적인 수열은 n개의 숫자마다 push와 pop을 수행해야 하기 때문에 +와 -의 출력은 2*n만큼 나옵니다.

 

코드

// 1874_스택 수열
#include <cstdio>
#include <stack>
using namespace std;

int arr[100001], n, flag = 0;
char result[200001];
stack<int> stk;

int main() {
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  int arrcount = 0; // 수열에서의 index
  int rescount = 0; // +, -를 저장하는 result 배열의 index

  for (int i = 1; i <= n; i++) { // 입력은 오름차순으로 주어짐
    stk.push(i);                 // 오름차순으로 push
    result[rescount++] = '+';

    while (!stk.empty()) { // pop 할 수 있는 데까지 pop함
      if (arr[arrcount] == stk.top()) {
        stk.pop();
        arrcount++;
        result[rescount++] = '-';
        continue;
      }

      break; // pop 못하면 다음 push하러
    }
  }

  if (!stk.empty()) { // 만약에 스택에 숫자가 남아있으면 수열 완성 실패
    printf("NO\n");
    return 0;
  }

  for (int i = 0; i < n * 2; i++) { // 수열 완성, 출력은 2*n만큼
    printf("%c\n", result[i]);
  }

  return 0;
}