[1874] 스택 수열 - 스택 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

[ 문제 접근 ]

 

우선 틀렸다.  테스트 케이스는 전부 통과하는데 시간초과가 뜬다.

어디서 시간 복잡도가 올라 갔는지 잘 모르겠다..

 

문제와 정답 코드가 잊혀질때쯤 다시 풀어 봐야겠다.

---

[ 틀린 코드 ]

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>

using std::cout; using std::cin;
using std::vector;

int n;
vector<int> arr;
std::string answer = "";
bool flag=true;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	int b = n;
	while (b--) {
		int a;
		cin >> a;
		arr.push_back(a);
	}
	std::stack<int> st;
	
	int cnt = 0;
	int i = 1;
	while (cnt != n) {
		if (i == n+1) {
			cout << "NO";
			flag = false;
			break;
		}
		for (; i <= arr[cnt]; i++) {
			st.push(i);
			answer += "+\n";
		}
		while (st.top() == arr[cnt]) {
			st.pop();
			answer += "-\n";
			cnt++;
			if (cnt == n || st.empty())break;
		}
	}
	if (flag) {
		cout << answer;
	}


	return 0;
}

나는 입력을 vector로 다 받은 다음에 로직 처리 하려고 하는데 정답 코드들을 보면 한 글자 한 글자 입력 받을때 마다 로직 처리를 해주고 있다.

어떻게 다들 그렇게 생각했는지 궁금하다.

 

 

[ 정답 코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>

using std::cout; using std::cin;
using std::vector;

int n;
vector<int> arr;
std::string answer = "";
bool flag = true;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	int b = n;

	while (b--) {
		int a;
		cin >> a;
		arr.push_back(a);
	}

	std::stack<int> st;

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		st.push(i);
		answer += "+\n";
		
		while (!st.empty() && arr[cnt] == st.top()) {
			st.pop();
			answer += "-\n";
			cnt++;
			if (cnt >= n)break;
		}
	}
	if (!st.empty()) {
		cout << "NO";
	}
	else {
		cout << answer;
	}


	return 0;
}

 

[ 바킹독님 정답 코드 ]

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>

using std::cout; using std::cin;
using std::vector;

int n;
std::string answer = "";
bool flag = true;
std::stack<int> st;
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	int idx = 1;
	while (n--) {
		int cur;
		cin >> cur;
		while (idx <= cur) {
			st.push(idx++);
			answer += "+\n";
		}
		if (st.top() != cur) {
			cout << "NO\n";
			return 0;
		}
		st.pop();
		answer += "-\n";
	}
	cout << answer;

	return 0;
}

 

---

[ Key Point ]

 

👉 while 문 안의 조건문도 순서대로 처리된다.

while (!st.empty() && arr[cnt] == st.top()) {
			st.pop();
			answer += "-\n";
			cnt++;
			if (cnt >= n)break;
	}

 

st 이 empty 상태에서 st.top() 함수를 호출하면 런타임 오류가 난다.

그래서 !st.empty() 를 while 문에 같이 써줬는데 오류가 나길래  while문 안의 조건문 순서를 바꿔보니 오류가 사라졌다.

 

arr[cnt] == st.top()  &&   !st.empty()   이렇게 하면 오류가 발생

!st.empty()         &&   arr[cnt] == st.top()   이렇게 하면 오류가 나지 않는다.

 

새로운거 알게 됐다.

 

 

👉 3번째 정답 처럼 푸는게 제일 깔끔하다.

---

[ 다른 사람 풀이 ]

 

ref :: https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/solutions/1874.cpp