[백준] 2493번 탑 - C++

소스코드

#include <stdio.h>
#include <stack>
#include <utility>

using namespace std;

int main(){
	stack<pair<int, int> > st;
	
	int N;
	scanf("%d", &N);
	
	int temp, i;
	for(i=1; i<=N; i++){
		scanf("%d", &temp);
		
		while(!st.empty()){
			if (st.top().first > temp){
				printf("%d ", st.top().second);
				break;
			}
			st.pop();
		}
		
		if(st.empty() == true) {
			printf("0 ");
		}	
		st.push(make_pair(temp, i));		
	}
}

스택을 사용해야 하는 것 같기는 했지만 (한쪽에서만 pop, push 발생) 발상이 어려웠기에 검색을 참고했다. 추후에 스스로의 힘으로 다시 풀어보야아 할 듯..

해설

우선 stack 하나만을 사용하였고, pair <int,int> 자료형을 이용해 하나의 stack만 사용해 풀었다. 처음 풀 때 시간 초과가 떴는데, cin cout 대신에 scanf printf를 사용하니 시간 초과가 뜨지 않고 해결할 수 있었다. (cin cout 자체가 시간이 많이 소요된다고 한다. 이런 문제로 해결못하신 분들이 종종 보였음..!)  

 

아래 stack으로 구현한 내용을 살펴보면, 

	for(i=1; i<=N; i++){
		scanf("%d", &temp);
		
		while(!st.empty()){
			if (st.top().first > temp){
				printf("%d ", st.top().second);
				break;
			}
			st.pop();
		}
		
		if(st.empty() == true) {
			printf("0 ");
		}	
		st.push(make_pair(temp, i));		
	}

우선 temp로 값 하나만 scan한다. 이 때 끝까지 stack에 값이 없으면 (끝까지 pop 되었거나 = stack에 존재했던 값들이 모두 지금 현재 들어온 값보다 작은 값 뿐이라 수신이 안 되는 경우, 아예 처음부터 stack에 값이 없었던 경우)  비교 불가능한 것이므로 그냥 0을 출력해 준다.

stack에 값이 있는 동안은 (계속 비교: while문 사용) 현재 들어온 값들과 있었던 stack의 값을 비교해주는데, 이때 stack에 있는 값이 현재 들어온 값보다 작을 경우 어차피 무의미하므로 (예를 들어 원래 7이 존재했는데 들어온 값이 9-> 어차피 뒤에 있는 탑들의 신호도 9가 수신하게 되므로 7은 의미 없다. 9가 수신 못하는데 7이 수신 가능한 값은 없다.) 그냥 pop(); 하여 삭제해 준다. 그리고 다시 그 뒤에 있는 값과 비교를 반복하다, 비교 중 temp 값보다 stack의 top 값이 더 클 경우 그 탑에서 수신하는 것이므로 그 st.top()의 second 값을 출력해준다.

마지막으로 현재 탑을 stack에 push해준다. (위치가 우선이므로, 이 뒤에 오는 temp값들을 수신할 가능성이 있음.)

 

나중에 꼭 다시 풀어보자!