[백준 2493번 C++] 탑

2493번: 탑 (acmicpc.net)

2493번: 탑

 

---

탑을 배열로 입력을 받아서

가장 오른쪽부터 자신보다 높은 가장 가까운 왼쪽 탑을 새로운 배열에 저장시키면 된다

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n;
    
    vector<int> v;
    vector<int> r;
    
    for(int i=0; i<n; i++){
        cin >> m;
        v.push_back(m);
    }
    
    r.push_back(0);
    for(int i=1; i<n; i++){
        int m = i-1;
        
        while(m>=0){
            //v[i]보다 높은 탑을 발견했을 때
            if(v[m] > v[i]){
                r.push_back(m+1);
                break;
            }
            //v[i]보다 높지 않을 때
            else{
                m--;
            }
        }
        if(m<0) r.push_back(0);
    }
    
    //r 벡터를 출력
    for(int i=0; i<n; i++){
        cout <<  r[i] <<" ";
    }
    
    return 0;
}

이렇게 가장 직관적으로 해서 잘 출력되는 것을 확인하고 제출하니

시간 초과

..

 

검색해보니 스택을 이용하면 해결할 수 있다고 한다

 

[C++] 백준 2493번 : 탑 (tistory.com)

[C++] 백준 2493번 : 탑

백준 - 2493 탑 :: 화투의 개발 블로그 (tistory.com)

백준 - 2493 탑

스택으로 수정해도 시간 초과가 떴는 데, 

가장 위 두 줄을 추가해주니까 해결됐다.

cin.tie(0);
ios_base::sync_with_stdio(false);

 

그렇게 최종 코드는

#include <iostream>
#include <stack>

using namespace std;

int main() {
	cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, m;
    stack<pair<int, int>> s;
    
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> m;
		
		//스택이 쌓여있으면 자신보다 큰 게 존재
		while (!s.empty()) {
		    //자신보다 큰 탑을 찾으면
			if (m < s.top().second) {
				cout << s.top().first << " ";
				break;
			}
			s.pop();
		}
		
		//스택이 비어있으면 자신보다 큰 게 없는 것
		if (s.empty()) cout << 0 << " ";
	
		
		s.push({ i + 1, m });
	}
}