[백준/c++] 1874 - 스택 수열

오늘부터 블로그에 문제 풀이를 적기로 했다! 😊

요즘 예전에 풀었던 문제를 다시 풀고 있어서

현재 코드 / 예전 코드 를 비교해볼 때가 많은데,

도무지 어떤 방식으로 푼 건지

머리로 이해할 수 없어서 과정을 기록해보려고 한다.

미숙하지만 이것도 연습하다 보면 익숙해지겠지.

아무튼, 풀어보겠다! 

---

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

1874번: 스택 수열

 

---

1) 풀이

이 문제를 처음 풀 때는 문제 자체를 이해할 수 없었다.  😢

그래서 유튜브의 도움을 살짝 빌렸다! (링크는 '3) 참고 사이트' 에 첨부)

 

스택의 특성을 고려해 다음과 같이 큰 갈래로 나눠서 생각해보았다.

 

1. 수열 스택이 비어있는 경우

2. 수열 스택이 비지 않은 경우

 

그리고 큰 갈래 안에 작은 갈래로 나눠서 생각해보았다.

 

• "NO"를 출력하는 상황
• PUSH가 일어나는 상황
• POP이 일어나는 상황

이제 이 갈래들을 큰 갈래 안에서 나눠서 생각해보았다.

 

수열 스택이 비어있는 경우

1. "NO"

- 입력된 값이 스택에 입력되었던 최댓값보다 작은 경우

2. PUSH

- 전자의 경우를 제외한 모든 경우

3. POP

- 입력된 값까지 PUSH가 일어난 후

※스택이 비어있는 경우, 반드시 PUSH가 일어나야만 POP 가능! 

 

수열 스택이 비어있지 않은 경우

1. "NO"

- 입력된 값이 스택에 입력되었던 최댓값보다 작고, 스택의 top보다 큰 경우

2. PUSH

- 입력된 값이 스택에 입력되었던 최댓값보다 크고, 스택의 top보다 큰 경우

3. POP

- 입력된 값까지 PUSH가 일어난 후

- 입력된 값이 스택에 입력되었던 최댓값보다 작거나 같고, 스택의 top보다 작거나 같은 경우

 

 

모든 경우를 조건문으로 나눠서 코드를 짜보았더니, 정답을 맞았다!

 

 2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int n; 
stack<int>st; // 수열 스택
queue<char>q; // +, -를 저장해둘 queue. NO가 입력해야 하는 경우때문에 즉시 출력하지 않고 queue에 저장해둔다.
int c; //수열을 이루는 정수
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int maxim = 0; //스택에 입력되었던 최댓값.
	cin >> n;
	while (n--) {
		cin >> c;
		if (st.empty()) { //스택이 비어있는 경우
			if (maxim > c) { //NO가 출력될 경우. 출력후 바로 종료.
				cout << "NO" << '\n';
				return 0;
			}
			else { //push가 필요한 경우
				for (int i = maxim + 1; i <= c; i++) {
					q.push('+');
					st.push(i);
					if (i == c) { //POP. (해당 값까지 PUSH가 일어난후)
						q.push('-');
						st.pop();
					}
				}
			}
		}
		else {//스택이 비어있지 않은 경우
			if (maxim > c && st.top() < c) { //NO가 출력될 경우. 출력후 바로 종료.
				cout << "NO" << '\n';
				return 0;
			}
			else if (st.top() < c && maxim < c) {
				//push
				for (int i = maxim + 1; i <= c; i++) {
					q.push('+');
					st.push(i);
					if (i == c) { //POP. (해당 값까지 PUSH가 일어난후)
						q.push('-');
						st.pop();
					}
				}
			}
			else if (st.top() >= c && maxim >= c) {//pop
				while (st.top() != c) {
					q.push('-');
					st.pop();
				}
				q.push('-');
				st.pop();
			}
		}
		maxim = max(maxim, c); //새로 입력된 값과 기존의 최댓값을 비교해 더 큰 값으로 최댓값 갱신.
	}
	while (!q.empty()) {
		cout << q.front() << '\n';
		q.pop();
	}
	cout << '\n';

}

3) 참고자료

https://www.youtube.com/watch?v=byCxMbgzEVM