[BOJ] 백준 1874 스택수열

1874번 스택수열

위 문제는 단계별 문제 중 스택 문제에 해당하는 문제이다. 백준에서 스택 단계에서 만날 수 있는 문제이며, push / pop을 이용해 stack을 이용해 해당 수열을 만들 수 있는지 판단하는 문제이다. 해당 문제는 정보처리기사 시험에도 종종 등장하곤 한다.

현재 업무에서 C++을 언어를 주 언어로 하다보니, C++로 모든 것을 연습하고자한다. 따라서 이번 문제도 C++를 보고 풀었으나, 다른 사람들이 푼 소스코드를 보거나, 지식이 부족한 부분에 대해 추가적으로 정리하고자 한다.

문제

스택수열는 push 와 pop을 활용해 입력으로 받은 수열을 만들 수 있는지를 물어보는 문제이다. 구체적으로, n만큼의 연속적인 수를 입력받을 경우 push / pop을 이용해 입력으로 받은 스택 수열을 만들 수 있는지 판단하고 만들 수 있을 경우 + (push) / - (pop) 을 출력해주면 된다. 만약 되지 않을 경우 “NO” 를 출력하면 된다.

수열의 생성이 가능할 경우를 보자 스택수열 출력

문제 풀이

이 문제를 풀기 위해서는 스택그림을 그려가며 push / pop 동작을 이해야한다. 문제풀이

위의 그림을 보자. 1,3,2의 입력을 stack 기능으로 출력이 가능할까를 예시로 들어보았다. 결과적으로는 가능하다. 1을 먼저 push하고 pop을 하면 1이 출력가능하다. 3을 출력하기 위해서는 2,3을 push하고 pop을 하면 3도 출력가능하다. 마지막으로 stack 내 남은 2을 출력하면 2도 출력가능하다. 모든게 다되는건 아닌가? 하는 생각이 들 수 있다. 그럴 경우 1,4,2,3 을 stack으로 출력해보자. 아마 NO 라는 출력이 나올 것이다.

문제를 해결하기 위한 코드는 아래와 같다.

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

using namespace std;

int main()
{
  stack<int> st;
  vector<char> v;
  int N, top = 0;

  cin >> N;

  while (N--) {
    int tmp;
    cin >> tmp;
    while (top < tmp) {
      top++;
      v.push_back('+');
      st.push(top);
    }

    if (st.top() == tmp) {
      v.push_back('-');
      st.pop();
    }
  }

  if (!st.empty()) cout << "NO" << endl;
  else {
    for (auto a : v) {
      cout << a << "\n";
    }
  }
}

코드에서 중요하게 생각해야할 부분은 2가지이다.

입력 받은 값보다 현재 stack의 값이 작다면 모든 것들을 push 한다.
top과 같은 경우 pop 연산을 통해 stack에서 제거한다
- 다를 경우 볼 필요도 없이 break연산을 해도 된다. 다만, 소스코드가 안이뻐서 바로 break연산을 하지는 않았다.

생각하지 못한 부분

문제를 해결하면서 생각하지 못해 틀린 부분이 두 가지가 존재한다.

char 배열을 통해 문제를 해결할 경우 크기를 고려하자.

int main()
{
  stack<int> st;
  char v[200001];
  int N, idx = 0, top = 0;

  cin >> N;

  while (N--) {
    int tmp;
    cin >> tmp;
    while (top < tmp) {
      top++;
      v[idx++] = '+';
      st.push(top);
    }

    if (st.top() == tmp) {
      v[idx++] = '-';
      st.pop();
    }
  }

  if (!st.empty()) cout << "NO" << endl;
  else {
		for (int i = 0; i < idx; i++) {
			cout << v[i] << "\n";
		}
	}
}

char 배열을 사용할 경우 위와 같이 사용하면 된다. 어려울 것 없이 vector에서 char 배열로 변경하면된다. 다만, char 배열을 잡을 경우 사이즈를 주목하자 처음 틀렸던 부분인데, 생각해보면 출력이 가능한 케이스가 입력받을 수 있는 갯수의 2배가 되야한다. 즉, push와 pop을 통해 출력하기 떄문에 입력의 최대값인 10만의 곱하기 2배만큼의 배열 공간을 생성해야한다.

“endl” 연산 사용 주의

C++을 하다보면 자연스럽게 endl 이라는 io 조작자를 배운다. IO 조작자 같은 경우 이전 포스팅 에서 setprecision()를 다룰때 언급했다. endl 같은 경우 개행문자 역할을 하는데 stream을 조작한다. 하지만 상당히 많이 사용되기 떄문에 iomanip 헤더파일이 아닌 iostream에 존재한다. 다만, endl을 사용할 때 주의할 점은 endl은 함수 로 구성되었다는 것이다. endl에 대한 자세한 설명은 여기 를 클릭해 확인해보자. 함수를 지속적으로 호출하는 것은 시간과 메모리에 상당한 부담이 된다. 따라서, 의도적인 데어터 입력을 통해 출력값을 나타내는 문제 풀이용에서는 endl보다 \n 개행문자를 사용하도록하자. \n 개행문자 같은 경우 함수 호출이 아니기 때문에 속도와 메모리에 영향을 미치지 않는다. 이 부분을 몰라 3번의 runtime 오류를 만났다 ㅠㅠ,,

스택을 이용해 1874 문제를 풀어보자

1874번 스택수열

문제

문제 풀이

생각하지 못한 부분