[1874]스택수열(C++)

1. 문제

www.acmicpc.net/problem/1874

1874번: 스택 수열

2. 접근 방법

1) 스택에는 값을 "오름차순"으로 넣을 수 있다 => 내가 이번에 찾을 순열 값과 스택의 top을 비교해보면 스택에 내가 찾은 값이 있는지 알 수 있다. 한번이라도 넣었는지를 알 수 있다. 

         - s.top() < v[idx] : 아직 스택에 v[idx]가 들어온 적이 없거나 혹은 전에 한번 넣었는데 pop하느라 없어진 경우 두 가지가 있다. 전자의 경우는 s.top() == v[idx]이 될 때까지 push하면 되고, 후자의 경우는 계속 push하다가 이번에 넣을 값이 N보다 커질 때 "NO"를 리턴하도록 한다.

 

        - s.top() > v[idx] : 스택에 값이 들어있거나, 값이 들어간 후 pop에 의해 없어진 경우 두가지가 있다. 전자의 경우는 s.top() == v[idx]이 될 때까지 pop하면 되고, 후자의 경우는 계속 pop하다가 s.empty()가 돌 것이므로 이 때 "NO"를 리턴하도록 한다.

 

         -처음에 v[idx]와 cnt(스택에 이번에 넣을 값)으로 비교를 해야 하는지, s.top()으로 비교를 해야 하는지 고민을 했다. 그런데 전자의 경우는 그냥 스택에 cnt 값을 넣은 적이 있었는지만 알뿐, 어느 차례에서 스택에 값을 빼야하는지 알 수 없었다. 반면 s.top() == v[idx]일 때 스택에서 꺼내서 수열을 완성 시킬 수 있으므로, s.top과 비교했다.

 

 

2) s.top() == v[idx]가 될 때까지 양방향으로 while문을 돌려 연산한다.( s.top< v[idx]면 s.top == v[idx]가 될 때까지 push를 수행. s.top > v[idx]면 s.top == v[idx]가 될 때까지 pop을 수행) 이 때, 문제의 조건 등을 추가한다(cnt <= N, !s.empty())

 

 

3) 만약 s.top() == v[idx]를 만족하지 못하고 문제의 조건에 의해 while문을 빠져나온다면 "NO"를 출력, 만약 s.top()== v[idx]를 만족한다면 s.pop()을 수행하고 다음 순열값을 조사한다.

 

3. 실수했던 부분 & 처음 알았던 부분

1) stack의 top 비교 전에 반드시 !s.empty() 확인할 것

-나의 경우 if( s.top() == v[idx] && !s.empty())로 써서 처음에 런타임 에러가 났었다. 같은 if문 내라도 반드시 empty를 확인 후 !! top 비교할 것 

 

 

2) 맨 처음 s.empty()이면 스택에 값을 넣는 경우에 cnt <= N의 조건도 추가했다.

- 물론 스택에 들어갈 값이 1~N사이 범위이므로 다음 조건을 추가하는게 맞지만, 그럼 스택이 비어있는데 값이 안들어가서 .. 후에 while()문 비교할 때 s.top() < v[idx]에서 런타임 에러가 발생할 수 있으므로, 

- > 일단 스택이 비면 값을 넣고 => 마지막에 조건을 확인하는 것이 편함!! 

 

 

3) char는 ''이고, string은 "" 이다.

 

 

4) N의 범위가 크면 시간초과를 유도하는(?) 문제일 수 있으므로 , endl 대신 "\n" 사용하고 main 앞 부분에 버퍼 조건 추가하기

 

4. 코드

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	
	//수열 입력받기 
	vector<int> v(N);
	for(int i=0;i<N;i++) 
		cin >> v[i];
	
	//결과 값을 저장할 벡터 
	vector<string> answer;

	//스택 이용해서 순열 구하기
	stack<int> s;
	int cnt = 1; //이번에 스택에 넣을 값 
	
	for(int idx= 0; idx < N; idx++) { //이번에 구해야 할 순열의 인덱스
		if(s.empty()) { 
			s.push(cnt++);
			answer.push_back("+");
		}
		//스택에 이미 구해야 할 숫자가 있으면 pop,없으면 push
		while(s.top() < v[idx] && cnt <= N) {
			s.push(cnt++);
			answer.push_back("+");
		}

		while(!s.empty() && s.top() > v[idx]) {
			s.pop();
			answer.push_back("-");
		}
		
		//순열을 만들 수 있음
		if( !s.empty() && s.top() == v[idx]){
			s.pop();
			answer.push_back("-");
		}
        	else {	
			answer.clear();
			answer.push_back("NO");
			break;
		} 
	}
	for(auto x : answer) 
	 	cout << x << "\n";
	
	return 0;

}