[알고리즘][스택] 1874번 스택 수열 | baekjoon 문제 풀이

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

1874번: 스택 수열

 

 

문제

수열이 주어지면, 해당 수열을 스택을 통해 만들 수 있는지 알아내는 문제

주의사항: 모든 값들은 오름차순으로 삽입되어야 함

 

 

풀이

도합 3시간 정도만에 겨우 성공했다. 문제가 어렵다기보다는, 내가 이해를 잘못해서 원하는 결과가 잘 안 나왔던 것 같다.

 

그리고 아쉬웠던 점은, 스택만 이용하여 이것저것 조건을 넣어 풀다보니 실행 시간이 오래 걸린 것 같다.

 

 

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

int arr[100000]; // 수열을 담는 배열
bool isUsed[100001] = { false, }; // 해당 값이 쓰였는지 알기위한 bool type 배열
string str = ""; // char type의 결과를 담기위해 string 변수 사용
stack<int> st; // 사용할 스택

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n, count = 0; cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	
	bool result = true; // 수열을 만들 수 있는지 없는지 여부

	while (result && (count < n)) { // result가 true이거나 모든 수열을 다 검사하기 전까지 계속 loop
		if (st.empty()) { // 쓰이지 않은 값 중에 arr[count]보다 작은 값 중, 최솟값을 찾아서 넣어주기 -> 없으면 result = false;
			int target = arr[count];
			bool b = false; 
			for (int i = 1; i <= target; i++) {
				if (!isUsed[i]) {
					st.push(i);
					str += '+';
					isUsed[i] = true;
					b = true;
					break;
				}
			}
			if (!b) { // 한번이라도 push가 있었는지 check -> 없었으면 result = false;
				result = false;
				break;
			}
		}

		if (arr[count] == st.top()) { // 만약 stack의 top에 arr[count]가 있다면 -> 출력
			st.pop();
			str += '-';
			count++;
		}
		else if (arr[count] > st.top()) { // 만약 stack의 top이 arr[count]보다 작다면 -> push
			int top_p1 = st.top() + 1;
			int target = arr[count];
			if(isUsed[target]) { // 찾아야 하는 target 값이 이미 쓰였다면 -> result=false;
				result = false;
				break;
			}
			for (int i = top_p1; i <= target; i++) {
				if (!isUsed[i]) {
					st.push(i);
					str += '+';
					isUsed[i] = true;
				}
			}
		}
		else { // 만약 stack의 top이 arr[count]보다 크다면 -> pop
			int top = st.top();
			int target = arr[count];
			bool b = false; 
			for (int i = top; i > target; i--) {
				if (st.top() == i) {
					st.pop();
					str += '-';
					b = true;
					count++;
				}
			}
			if (!b) { // 한번이라도 pop이 있었는지 check -> 없으면 result = false;
				result = false;
				break;
			}
		}
	}

	if (result) {
		int str_length = str.length();
		for (int i = 0; i < str_length; i++) {
			cout << str[i] << '\n';
		}
	}
	else cout << "NO";
}

 

생각보다 내 코드가 너무 복잡해보였다.

내가 쓸데없는 예외까지 생각한건가?

아무튼 그래서 다른 코드를 참고하여 더 간단하게 수정해보았다.

 

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

string str = ""; 
stack<int> st; 

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n; cin >> n;
	int count = 1;
	
	bool result = true; 

	for (int i = 0; i < n; i++) {
		int num = 0; cin >> num; // 이렇게 되면, 굳이 arr배열과 isUsed배열을 만들 필요가 없다

		while (count <= num) { // 무조건 오름차순이고 한 번 stack에 들어간 값이 또 들어가지 않으니까 이렇게!
			st.push(count);
			count++;
			str += '+';
		}

		if (st.top() == num) {
			st.pop();
			str += '-';
		}
		else { 
			cout << "NO";
			return 0;
		}
	}

	int str_length = str.length();
	for (int i = 0; i < str_length; i++) {
		cout << str[i] << '\n';
	}
}

다른 코드 참고하니까 이제 문제가 이해된 것 같다...^^ 

메모리 절약은 물론 시간도 1/20배 이상 감소했다

 

앞으로 문제 더 꼼꼼히 읽고 단순화해서 호다닥 풀자...!