[백준] 1874번: 스택 수열 C++로 풀어보기

1874번 풀이

어떻게 풀까? (문제를 풀고 처음 든생각)

문제를 다시 읽어봐도 예제 입력값이 어떻게 예제 출력값을 유도하는 지 이해가 가지 않았다. 그래서 천천히 단계별로 생각해 보기로 했다.

 

배열 : 4 3 6 8 7 5 2 1
지금 배열은 4를 가리키고 있다. 4를 처리하면 다음 배열값으로 넘어간다.


1. stack | vector
    1

2. stack | vector
     2
     1

3. stack | vector
     3
     2
     1

4. stack | vector   <- 지금 배열이 가리키는 값이랑 같다. 일단 stack에 push
     4
     3
     2
     1

5. stack | vector <- stack을 pop하고 그 값은 vector 첫번째 값이 된다.
     3        4
     2
     1

6. stack | vector <- 지금 배열이 가리키는 값인 3을 또 pop하고 vector로 옮긴다.
     2        4
     1        3

7. stack | vector <- 지금 배열이 가리키는 값인 6보다 top이 작으니 top이 6이 될 때까지 계속 push한다.
     5        4
     2        3
     1

8. stack | vector 
      6       4
      5       3
      2
      1

9. stack | vector <- 지금 배열이 가리키는 값인 6을 pop한다.
     5        4
     2        3
     1        6

10. stack | vector <- 지금 배열이 가리키는 값인 8보다 top이 작으니 top이 8이 될 때까지 계속 push한다.
      7        4
      5        3
      2        6
      1

11. stack | vector
      8         4
      7         3
      5         6
      2
      1

12. stack | vector <- 지금 배열이 가리키는 값인 8이 top이므로 8을 pop한다.
      7         4
      5         3
      2         6
      1         8

13. stack | vector <- 지금부터는 배열이 가리키는 값이 stack의 top이 아니면 'NO'를 출력하고 프로그램을 끝내고, 아니라면 계속 pop한다.

 

 

수열이 만들어지려면?

top이 현재 수열이 가리키는 값보다 작다면
->  push

top이 현재 수열이 가리키는 값과 같으면
-> pop

top이 현재 수열이 가리키는 값보다 크다면

-> 'NO' 출력

 

코드

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vector <int> v;
	vector <char> result;
	stack <int> s;
	int n;

	cin >> n; // 정수 개수 입력
	int maxx = n;

	while (n--) {
		int x;
		cin >> x;
		v.push_back(x);
	}

	int i = 1;
	vector<int>::iterator it = v.begin();


	// 일단 0을 스택에 집어넣는다.
	s.push(0);
	
	while (it != v.end()) {
		if (s.top() < *it) { // top이 현재 수열이 가리키는 값보다 작다면
			s.push(i);
			result.push_back('+');
			i++;
		}
		else if (s.top() == *it) { // top이 현재 수열이 가리키는 값과 같다면
			s.pop();
			result.push_back('-');
			it++;
		}
		else if (s.top() > *it) { // top이 현재 수열이 가리키는 값보다 크다면
			cout << "NO";
			return 0;
		}
	}
	


	for (auto it2 = result.begin(); it2 != result.end(); it2++) {
		cout << *it2 << '\n';
	}


}

스택에 0을 집어넣는 이유는 스택이 비어있는데 top을 부르면 에러가 나기 때문이다.

(이것때문에 1시간은 날아간 거 같다. 원래는 !(s.empty())를 썼었는데 앞으로는 그냥 0을 넣는게 나은 것 같다.)

 

top이 현재 수열이 가리키는 값보다 크면 "NO"를 출력하고 프로그램을 종료하면 된다.

돌이켜보면 참 간단한 방법이었다. 이 생각이 안 떠올라서 계속 빙빙돌다가 또 1시간을 날려먹었다..

결과

1875번 결과

후기

이번 문제를 풀기 위해서 2시간을 넘게 집중했지만 답이 나오지 않아 chatGPT랑 구글 블로그 검색을 참조했다.

메인 아이디어는 일치했지만 너무 복잡하게 생각해서 꼬인 것 같다.

스택을 이용한 문제를 풀 때는 스택이 비어있을 때를 꼭 고려해보자.