[자료구조] 백준 1874번: 스택 수열 (C++)

다음 문제를 풀 때 부호가 나올 수 있는 경우는 구현을 했지만 "NO"가 출력되어야 하는 부분을 처리하지 못했다.

내가 짰던 코드는 다음과 같다.

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

int main() {
	int n;
	cin >> n;
	stack<int> idx;
	vector<int> sample;
	vector<char> chart;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		sample.push_back(a);
	}

	int max = sample[0];
	for (int i = 1; i <= sample[0]; i++) {
		idx.push(i);
		chart.push_back('+');
	}
	int nextNum = sample[0] + 1;

	vector<int> popNum;

	for (int i = 1; i < sample.size(); i++) {
		if (sample[i] < max) {
			while (1) {
				if (idx.top() == sample[i]) {
					popNum.push_back(idx.top());
					idx.pop();
					chart.push_back('-');
					break;
				}
				else {
					popNum.push_back(idx.top());
					idx.pop();
					chart.push_back('-');
				}
			}
		}
		else if (sample[i] > max) {
			while (1) {
				if (idx.top() == sample[i]) {
					popNum.push_back(idx.top());
					idx.pop();
					chart.push_back('-');
					break;
				}
				else {
					if (nextNum > n) {
						cout << "NO" << '\n';
						return 0;
						break;
					}
					idx.push(nextNum);
					nextNum++;
					chart.push_back('+');
				}
			}
		}
	}

	for (int i = 0; i < chart.size(); i++) {
		cout << chart[i] << '\n';
	}

	return 0;
}

코드가 꽤 길고, 여러 번 수정하다 보니 'max의 역할이 무엇이었는지' '이럴 때 "NO"가 나오는 것이 맞는지' 혼란이었다.

첫 번째 수를 바로 반복문 안에서 처리하는 방법도 해결 하지 못 해서 상단에서 먼저 처리해주었었다.

그래서 답을 참고하였다.

>>자기 코드를 해석해야 하는 경우가 생길 때 그 문제는 다시 갈아엎어야 하는 거 같다.

 

https://scarlettb.tistory.com/71

1874번 스택 수열 | Baekjoon BOJ 백준 1874 C++ 코드, 해설, 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
 
    int* arr = new int [n];
    stack<int> s;
    vector<char> v;
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    int j = 0;
    for (int i = 1; i <= n; i++) {
        s.push(i);
        v.push_back('+');
 
        while (!s.empty() && s.top() == arr[j]) {
            s.pop();
            v.push_back('-');
            j++;
        }
    }
 
    if (!s.empty()) {
        printf("NO");
        return 0;
    }
    else {
        for (int i = 0; i < v.size(); i++) {
            printf("%c\n", v[i]);
        }
    }
 
    return 0;
}

처음엔 for 안에 while이 이해가 안 가서 수 하나하나 넣어보면서 시뮬레이션해봤는데

느낀 점은 이렇다.

• stack에 중점을 두었다. (난 pop이 되어 사라진 수에 초점을 맞추다 보니 어긋난 거 같다.)
• for안에 while을 통해 즉각적으로 처리해주었다.
• 결국 문제의 조건이나 글을 읽어보면 stack안의 모든 수는 빠져나가야 한다.

이러한 점을 생각하였을 때 '어... 또 이런 비슷한 케이스 나오면 어떻게 접근해야 하지'

그다음엔 '당연히 문제 이름 조차 stack인데 stack에 초점을 둬야 했던 게 아닐까'라는 생각을 했다.

 

for 안의 while 구문 해석을 해보았다.

예시 1 시뮬레이션) 4 3 6 8 7 5 2 1

[1번째 for]
stack에 1이 들어감
v에 '+'
while의 조건과 맞지 않음

[2번째 for]
stack에 2가 들어감
v에 '+'
while의 조건과 맞지 않음

[3번째 for]
stack에 3이 들어감
v에 '+'
while의 조건과 맞지 않음

[4번째 for]
stack에 4가 들어감
v에 '+'
while의 조건과 맞음
    [4-1 while]
    stack에서 4가 빠짐 -> 수열 1번째 수 4
    v에 '-'
    j++ -> 수열 2번째 수(3)를 찾음
    [4-2 while]
    stack에서 3이 빠짐 -> 수열 2번째 수 3
    v에 '-'
    j++ -> 수열 3번째 수(6)를 찾음
while의 조건과 맞지 않음

[5번째 for]
stack에 5가 들어감
v에 '+'
while의 조건과 맞지 않음

[6번째 for]
stack에 6이 들어감
v에 '+'
while의 조건과 맞음
    [6-1 while]
    stack에서 6이 빠짐 -> 수열 3번째 수 6
    v에 '-'
    j++ -> 수열 4번째 수(8)를 찾음
while의 조건과 맞지 않음

[7번째 for]
stack에 7이 들어감
v에 '+'
while의 조건과 맞지 않음

[8번째 for]
stack에 8이 들어감
v에 '+'
while의 조건과 맞음
    [8-1 while]
    stack에서 8이 빠짐 -> 수열 4번째 수 8
    v에 '-'
    j++ -> 수열 5번째 수(7)를 찾음
    [8-2 while]
    stack에서 7이 빠짐 -> 수열 5번째 수 7
    v에 '-'
    j++ -> 수열 6번째 수(5)를 찾음
    [8-3 while] (stack 안에 7 -> 5인 이유는 6은 이미 6-1 while에서 빠져나왔기 때문이다)
    stack에서 5가 빠짐 -> 수열 6번째 수 5
    v에 '-'
    j++ -> 수열 7번째 수(2)를 찾음
    [8-3 while]
    stack에서 2가 빠짐 -> 수열 7번째 수 2
    v에 '-'
    j++ -> 수열 8번째 수(1)를 찾음
    [8-4 while]
    stack에서 1이 빠짐 -> 수열 8번째 수 1
    v에 '-'
    j++ -> 수열 8번째 수(1)를 찾음
while의 조건과 만족하지 않음 (stack이 비어있지 않을 때)
for도 n = 8까지 였기 for문이 끝남

stack은 결국 다 빠져나오게 되어서 "NO가 출력되지 않음"

예제 2의 경우 5에서 3으로 넘어갈 때
3이 while의 조건을 만족하지 않아서 3이 계속 스택에 남게 되어
"NO"가 출력된다.