[2493] 탑

분류

• 스택

 

문제

 

풀이

자신과 가까운 것부터 순차적으로 비교해봐야하므로 스택이 필요함을 알 수 있다.

모든 타워에 대해 조사해보아야 하므로 타워의 갯수 n개만큼 반복문을 돌아야 한다. 

 

방법에는 2가지가 있는데, for문에서 i=0부터 n까지 앞부터 실행하는 것과,

i=n부터 0까지 뒤에서부터 실행하는 방법이 있다. 

앞부터 실행하는 방법은, 이미 어떤 타워가 자신의 신호를 송신할지 결정된 타워들을 스택에 넣어두고,

결정을 해야하는 타워와 스택을 하나씩 비교해서, 현재 타워보다 높이가 낮으면 pop해간다.

1 ) 스택이 비어버리면, 자신 이전에 자신보다 큰 타워가 없어서 아무도 자신의 신호를 송신하지 못하므로 0이다

2 ) 자신보다 높은 타워가 발견되면, (스택을 이용해 가까운 순서대로 검사했으므로) 해당 타워의 인덱스가 답이된다.

 

여기서, 검사 중 자신보다 낮아서 pop되었다는 뜻은 

그 다음 타워로 넘어가도 어쩌피 고려할 가치가 없다는 뜻이므로 신경쓸 필요가 없다. 

 

 

이 그림이 사실 좀 헷갈릴 수도 있는데,, 원래대로 하면 5랑 비교한 순간 5가 스택에 들어가야한다.. 

뒤부터 실행하는 방법은, 반대로 뒤부터 검사하기 때문에 

맨 뒤 인덱스 타워부터 답이 정해지지 않은 타워를 스택에 넣어두고, 답이 정해지면( i-- 왼쪽으로 가면서 자신보다 큰 타워가 등장할 경우) 답을 작성하고 pop한다.

모든 타워가 답이 정해져 스택이 empty이면, 해당인덱스의 타워를 스택에 넣고, 왼쪽으로 이동하여 다시수행한다.

 

 

 

 

코드

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/**
 * [문제설명]
 * 탑은 모두 왼쪽 방향으로 레이저를 보냄
 * 각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 알아내는 문제
 *
 * [문제풀이]
 * 스택에 탑의 높이가 아닌 인덱스를 넣어야 함을 파악해 푸는 문제
 * 항상 스택의 top에 있는 인덱스의 탑 높이가 낮아야 함 (자신보다 높은 탑 중 가장 왼쪽에 있는 탑이 신호 수신하기 때문)
 * 1. (1 ~ n) 따라서 스택의 top에 있는 인덱스의 탑 높이가 현재 탑 높이와 같거나 낮다면 pop
 * 1. (1 ~ n) 앞의 과정이 끝난 후 스택이 비어있지 않다면 top에 있는 인덱스가 현재 탑의 신호를 수신하는 탑임
 * 2. (n ~ 1) 따라서 스택의 top에 있는 인덱스의 탑 높이가 현재 탑 높이보다 낮다면 현재 탑이 수신탑
 */

//1 ~ n 돌면서 수신탑 찾기
vector<int> transTop1(int n, vector<int> &num) {
    stack<int> st;
    vector<int> ans(n + 1, 0); //수신 탑 저장

    for (int i = 1; i <= n; i++) {
        while (!st.empty() && num[st.top()] <= num[i]) { //현재 탑 높이보다 st.top() 인덱스의 탑 높이가 같거나 낮다면 pop
            st.pop();
        }
        if (!st.empty()) ans[i] = st.top(); //스택이 비어있지 않다면 스택의 top에 저장된 인덱스가 현재 탑의 신호 수신탑
        st.push(i); //현재 탑 인덱스 스택에 push
    }

    return ans;
}

//n ~ 1 돌면서 수신탑 찾기
vector<int> transTop2(int n, vector<int> &num) {
    stack<int> st;
    vector<int> ans(n + 1, 0); //수신 탑 저장

    for (int i = n; i >= 1; i--) {
        while (!st.empty() && num[st.top()] < num[i]) { //현재 탑 높이보다 st.top() 인덱스의 탑 높이가 낮다면 현재 탑이 수신탑
            ans[st.top()] = i;
            st.pop(); //수신탑이 정해졌으므로 pop
        }
        st.push(i); //현재 탑 인덱스 스택에 push
    }

    return ans;
}

int main() {
    int n;

    //입력
    cin >> n;

    vector<int> num(n + 1, 0); //탑의 인덱스가 1부터 시작하므로 n+1 할당
    for (int i = 1; i <= n; i++)
        cin >> num[i];

    //연산
    //vector<int> ans = transTop1(n, num);
    vector<int> ans = transTop2(n, num);

    //출력
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }

    return 0;
}

 

 

pair를 이용하여 구하는 방법도 있다.

//2. 탑의 높이, 탑의 인덱스를 동시에 저장하는 pair stack사용

stack<pair<int, int>> s; // 탑의 높이, 몇번째 탑인지
vector<int> ans;

int main() {

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


    int N, num;

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> num;

        while (!s.empty()) {

            if (s.top().first >= num) {
                ans.push_back(s.top().second);
                break;
            }

            s.pop(); // 나보다 큰거는 pop해버리면안됨 , 작은건 앞으로 고려 x라서 pop


        }

        if (s.empty()) { //스택 끝까지 다찾아봤는데 더큰 탑이 없엇음 - > 0개
            ans.push_back(0);
        }
        s.push({num, i + 1}); // 지금 받은거 스택에 넣기
    }


    for (int i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }

}