[C++] 1874번 : 스택 수열

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

1874번: 스택 수열

풀이

사실 1시간 동안 이 문제를 풀지 못해 결국 답을 보았습니다.

추가로, 알고리즘을 아직 찍어먹는 수준으로 밖에 하지 않았지만 '알고리즘 문제 풀이 마인드'가 궁금하여 열심히 찾아본 결과

모두 중략하여 말하자면 '1시간이나 소비하지말고 30-45분 내에 떠오르지 않으면 넘기자'입니다.

 

1) 문제 이해

문제 이해를 못했는가? 아닙니다. 문제에서 정말 친절하게도 stack을 사용하라고 대놓고 명시해주고 있습니다.

'오름차순'의 수열을 stack의 push/pop method를 활용해 input의 순서로 pop할 수 있는가를 묻는 문제였습니다.

 

2) 전략 수립

n은 10만 time은 2초가 주어졌습니다. push/pop 연산이 O(1)이기 때문에 timeout이 일어나는 전략을 세우는 것이 세우지 않는 것보다 훨씬 어려울 것 같았습니다. 그래서 바로 Go!

int형 vector을 하나 더 선언하여 input 수열을 받고, 또 다른 int형 변수를 도입하여(오름차순을 위해) vector 요소들과 비교해나가며 적절한 로직으로 push&pop하고자 하였습니다.

사실 처음부터 이러한 전략을 생각한 것은 아니고 당연히 한 반복문 안에서 수열을 입력받으며 그리고 그것을 이용하여 해결하려 했습니다.만 무리였네요.

 

3)그래서 Feedback

결국 우리가 원하는 것은 push와 pop입니다. 어느 순간에 push되고 어느 순간에 pop되는지를 생각해야하죠?

push를 먼저 생각해봅시다.  언젠가 한 번 이런 idea가 쓰였던 것 같은데요?

만들어 내야하는 수열의 요소와 push할 것인지 결정해야하는 요소의 relation을 기민하게 파악해야했습니다.

좍 적어보면 보이거든요 ㅠㅠ

그 다음 pop을 생각하고 예외를 처리하려보니, 쉽지 않아요. s.empty()를 이용하여 처리하려고 했거든요..

그럼 다시 반대로 예외가 pop이고 NO를 따로 조건을 걸어준다면?

그렇게 또 좍 적으면 규칙이 보였어요.

 

사실 이렇게 푸는 게 맞는 지/이렇게 피드백하는 게 맞는 지 의구심이 많이 듭니다만. 뭐 어쩌겠어요. 정진하겠습니다..

+)vector<char>대신 string으로 받기!

아래는 정답 코드입니다.

 

정답 코드

 

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	stack<int> s;
	int num = 1;
	string str;
	while (n--) {
		int t;
		cin >> t;
		while (num <= t) {
			s.push(num++);
			str += "+\n";
		}
		if (s.top() != t) {
			cout << "NO\n";
			return 0;
		}
		else {
			s.pop();
			str += "-\n";
		}
	}
	cout << str;
}