백준,BOJ 2493번, 탑 C++ [CPP]

22.03.01 다시 풀어봄

 

모든 문제를 기록하긴 좀 그렇고

내가 이해가 한 번에 안된 것들을 다시 이해시키고자 한다.

 

www.acmicpc.net/problem/2493

2493번: 탑

 

---

 

문제를 보자.

탑을 하나씩 세운다고 생각하자. 

탑을 세울 때, 내 왼쪽에 수신할 탑이 없으면 0

수신할 탑이 있으면 해당 수신 탑의 index를 출력하면 되겠다.

 

5개의 탑 높이를 입력받는다.

6 9 5 7 4 순서대로 탑을 세우자.

 

위의 방법으로 해결하기 위해서는 왼쪽에 있는 탑들에 대한 정보를 알고 있어야 한다.

 

입력 받은 탑 :6

왼쪽에 있는 탑: 

비교할 것이 없음

-> 0출력

 

입력받은 탑: 9

왼쪽에 있는 탑: [6]

입력받은 값을 왼쪽에 있는 탑들과 비교 (가까운 것부터, 즉, 나중에 추가된 것부터)

6 비교

비교할 것이 없음

-> 0출력

 

입력받은 탑: 5

왼쪽에 있는 탑:[6,9]

입력받은 값을 왼쪽에 있는 탑들과 비교 (가까운 것부터, 즉, 나중에 추가된 것부터)

9비교

-> 9의 인덱스 출력

 

입력받은 탑: 7

왼쪽에 있는 탑: [6,9,5]

입력받은 값을 왼쪽에 있는 탑들과 비교 (가까운 것부터, 즉, 나중에 추가된 것부터)

5비교

9비교

-> 9의 인덱스 출력

 

입력받은 탑: 4

왼쪽에 있는 탑:[6,9,5,7]

7비교

-> 7의 인덱스 출력

 

 

위의 알고리즘을 해결하기위해

입력은 탑의 개수만큼 받아야하며

왼쪽에 있는 탑의 정보를 저장하기 위해 stk을 이용

해당 높이와 인덱스를 같이 출력하기위해 <pair<idx, h>>를 같이 저장

 

** 물론 위의 식은 문제의 흐름대로 내가 생각한 것이므로 실제 코드에서 스택에 남아있는 것과 틀릴 수 있다.

 

---

 

난 처음에 거꾸로 풀었다. 다 넣고 뒤에서부터 풀자..

 

뭐 그래도 되었을 것 같지만 헷갈렸다.

 

#1 틀린 내 풀이

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

using namespace std;

int arr[500001];


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

    int N;
    cin >> N;
    stack<int> stk;
    vector<pair<int, int>> v;
    
    
    //배열 초기화, 스택 입력
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        stk.push(a);
        arr[i] = 0;
    }

    int len = stk.size();
    
    //마지막건 어차피 0이므로 N-1번 반복
    for (int i = len - 1; i > 0; i--) {
        int a = stk.top();
        v.push_back({a,i});
        stk.pop();
        
        //수신탑 x 
        if (a > stk.top()) {
            continue;
        }
        
        //수신탑 o
        else {
            //현재 벡터에 들어있는 애들은 이 수신탑에 수신됨
            for (auto d : v) {
                arr[d.second] = i;
            }
            //벡터 초기화
            v.clear();
        }
    }

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


}

 

#2 다른 사람 풀이 참고

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, height;
    stack<pair<int,int>> stk;

    cin >> N;


    for (int i = 1; i <=N; i++) {
        cin >> height;
        while(!stk.empty()){
            if(stk.top().second>height){
                cout << stk.top().first << ' ';
                break;
            }
            stk.pop();
        }
        
        if(stk.empty()){
           // print out '0'
            cout << "0 "; 
        }

        //push
        stk.push({i,height});

    }




}

 

#3 맨 뒤에서부터 접근이 아닌 맨 앞에서부터 접근한 내 풀이

** 중간에 스택을 수정해도 되는 이유를 적었다.(21.11.25 업데이트)

#include <iostream>
#include <stack>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, h;
    stack<pair<int,int>> stk;

    cin >> N;
    
    for(int i= 1; i<=N; i++){
        cin >> h;
        int idx = i;
        
        //왼쪽 탑의 정보가 있으면 수신탑이 있는지 조사.
        //수신탑이 나올 때 까지 조사
        // -> 스택을 비워도 되느냐? 어차피 빠지는 거라면 나보다 작은 탑일텐데
        //빠진 탑들은 어차피 나보다 작아서 내 뒤에 있는 탑이 절대 송신에 성공할 수 없기 때문이다.
        if(!stk.empty()){
            while(h>stk.top().second){
                stk.pop();
                if(stk.empty()){
                    break;
                }
            }
        }
        
        //왼쪽 탑에 비교할 정보가 없으면
        if(stk.empty()){
            cout <<"0 ";
            stk.push({idx,h});
            continue;
        }
        
        cout << stk.top().first << ' ';
        stk.push({idx,h});
             
    }

}

 

 

---

 

4ms 정도 빨라졌다. 비슷한 시간이니까 같은 환경이라 치면 빨라지긴 했다.

 

아무튼 입력을 받으면서 비교를 해야할지

입력을 다 받고나서 비교를 해야할지 선택이겠지만 아마.

 

입력을 받으면서 비교가 된다면 입력을 받으면서 비교를 하는 것이 시간복잡도 상 이득이므로

그렇게 먼저 생각해봤어야 한다.

 

나는 해보지 않았기 때문에 시간초과도 나고 어려웠다.

 

 

** 반성할 점

입력을 받으면서 비교할 수 있는가? 그런 류의 문제인가?

 

---

? 다시 푸니까 아예다르게품..

#내 풀이

#include <bits/stdc++.h>

using namespace std;

int N;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    vector<int> vec(N);
    
    stack<pair<int,int>> stk; //기둥 번호, 높이
    
    for(int i = 1; i<=N; i++){
        int x;
        cin >> x;
        stk.push({i,x});
    }
    
    stack<pair<int,int>> temp;
    
    while(!stk.empty()){
        auto cur = stk.top();
        stk.pop();
        temp.push(cur);
        
        if(stk.empty())break;
        
        while(stk.top().second > temp.top().second){
            auto com = temp.top();
            temp.pop();
            vec[com.first-1] = stk.top().first;
            if(temp.empty())break;
        }
    }
    
    while(!temp.empty()){
        auto left = temp.top();
        temp.pop();
        vec[left.first-1] = 0;
    }
    
    for(auto x : vec){
        cout << x << ' ';
    }
    
    
    return 0;
}