[ C++ ] #2493 탑 (골드V)

https://www.acmicpc.net/problem/2493

문제

---

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. ( 1 ≤ N ≤ 500,000 )

둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. ( 1 ≤ 탑들의 높이 ≤ 100,000,000 )

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

 

 

 

풀이

---

 

.. 맨 오른쪽 탑부터 확인을 해야하기 때문에 맨 왼쪽 탑부터 차례대로 스택에 넣는다.

그 다음 하나씩 비교해야하는데 n 번째 숫자를 n-1개랑 비교해야하고 n-1번째는 n-2개랑 비교해야하고.. 이러면 운이 나쁜경우 총 비교해야하는 개수가 (n-1)!가 된다… 너무 오래걸리는데..

stack에 일단 차례대로 넣고 맨 위에서부터 확인해본다.

1. 내 앞에 있는 숫자가 나보다 작으면 pass
2. 내 앞에 있는 숫자가 나보다 크면 그 탑에 수신

맨 위 탑부터 보기때문에 num = n 으로 두고 n-- 하면서 탑의 순서를 고려해도될 것 같다.

정답은 큐에 넣어놓고 한번에 출력할 예정이고, 1번이 연속해서 일어난다면 몇번일어나는지 체크하여 그만큼 개수를 큐에 저장하는 것으로 해보자.

1차시도 : 실패 (잘못된 알고리즘)

• S : 탑
• temp : 다른 탑에 도달하지 못한 탑들 저장
• print : print할 내용 저장

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main(){

    int n, num, pass=0, before, now;
    stack<int> S;
    stack<int> print;
    stack<int> temp;

    cin>>n;

    for(int i=0;i<n;i++){  //스택에 다 저장하기
        cin>>pass;
        S.push(pass);
    }

    //비교하기
    before=S.top();
    for(num=n-1;num!=0;num--){

        S.pop();
        now=S.top();
        if(before>now){  // 지나가~
            temp.push(before); //지나간것들 저장
            print.push(0);
        }else{
            while(!temp.empty()){
                if((temp.top()<now)){ //지나간것들 중에 아직 부딛히지 못한것들 확인
                     temp.pop();
                     print.pop();
                     print.push(num);
                }else{
                    break;
                }
            }
            print.push(num);
        }
        before=now;
    }
    //print
    int size=print.size();
    cout<<"0";
    for(int i=0;i<size;i++){
        cout<<" "<<print.top();
        print.pop();

    }
return 0;
}

탑들을 보면서 즉시 판단하여 print 스택에 저장하였다.

탑들을 stack에 한번에 넣어 맨 오른쪽 탑부터 확인했으며 바로 왼쪽탑에 전송하면 해당 값을 바로 스택에 저장하고, 아니라면 일단 0을 저장하고 temp에 넣었다.

쭉 읽다가 조금 긴탑이 나타나면 0을 저장했던 즉 탑들 즉 temp에 있는 값들을 읽으며 조금 긴 탑에 전송하는지 확인한다.

하지만 이런식으로 print 에 내용을 넣다보니까 엄청 뒤늦게 전송하는 상황에 대처하지 못했다. print는 stack으로 저장하면 안될 것 같다. 그럼..어떻게 판단하지……

 

2차시도

1차시도에서 잘못된 점은 print를 stack으로 뒀다는것.

근데..

아..

아악.. 모르겠다

 

다른사람 코드 참조..

자존심..이 있기 때문에 전부 참조할 수 없다….

아이디어만 살짝 봤다.

1. 탑의 맨 앞부터 확인한다.
2. 핵심은 나보다 더 긴 탑이 오른쪽에 나타나면 나는 소용이 없다는 것이다!

나는 탑의 맨 뒤부터 보고 있었다. 이 점부터 잘못된 것이었다….

처음에 1번만 보고도 잘 이해되지 않아 2번 정보도 보게되었다.

앞에서부터 보다가 뒤에 나보다 긴 탑이 들어온다면 해당 탑과 그 뒤에 탑 모두 나에게 수신하지 않는다.

더이상 나는 필요가 없고 내 앞에 있는 탑들 중에 새로들어온 탑보다 긴 탑들만 의미 있게 된다.

위 내용을 기반으로 간단한 알고리즘을 보자.

1. 현재 탑과 스택에 있는 탑을 비교하여 송신할 탑을 찾기 위해 아래 과정을 반복한다.
   1. 송신할 탑이 아니라면, 즉 현재 탑보다 낮다면 pop한다.
   2. 송신할 탑이라면, 즉 현재 탑보다 높다면 해당 탑의 index를 출력한다.
   3. 스택이 비어있다면 송신할 탑이 없는것이기 때문에 0을 출력한다.
2. 현재 탑을 스택에 push한다.

현재 탑이 무슨 탑에 도달했는지에 대한 정보도 필요하기 때문에 pair<int, int> 를 저장하는 stack을 이용한다. 앞 int에는 인덱스, 뒤 int에는 길이 정보를 저장한다.

문제에 있는 예시로 다시 생각해보자

5
6 9 5 7 4

1. input: 6 / stack :
   stack에 (1,6) push
   stack이 비어있기 때문에 송신할 곳이 없다. 0을 출력한다.
2. input: 9 / stack : (1,6)
   stack의 top이 더 작으면 popstack에 (2,9) push
   stack이 비게 되면 0 출력
   stack이 비어있지 않기 때문에 stack의 top과 크기비교
   
3. input: 5 / stack : (2,9)
   stack의 top이 더 작으면 pop, 하지만 stack의 top이 더 크기 때문에 스택 top의 index 출력 (2)
   stack에 (3,5) push
   stack이 비어있지 않기 때문에 stack의 top과 크기비교
4. input: 7 / stack : (2,9), (3,5)
   stack의 top이 더 작아서 pop, 그 다음 top 과 크기비교stack에 (4,7) push
   stack의 top(9)이 더 크기 때문에 9의 index 출력 (2)
   stack이 비어있지 않기 때문에 stack의 top과 크기비교
5. input: 4 / stack : (2,9), (4,7)
   stack의 top이 더 크기 때문에 스택 top의 index 출력 (4)
   stack에 (5,4) push
   stack이 비어있지 않기 때문에 stack의 top과 크기비교

 

code

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main(){

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

    stack<pair<int, int> > S;
    int n=0,h=0;

    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>h;
        //현재 탑과 스택에 있는 탑을 비교하여 송신할 탑을 찾기
        while(!S.empty()){

            if(S.top().second < h){  //송신할 탑이 아니라면, 즉 현재 탑보다 낮다면 pop
                S.pop();
            }else{   //송신할 탑이라면, 즉 현재 탑보다 높다면 해당 탑의 index를 출력
                cout<<S.top().first<<" ";
                break;
            }
        }
        if(S.empty()) cout<<"0 ";  //스택이 비어있다면 송신할 탑이 없는것이기 때문에 0을 출력

        //현재 탑을 스택에 push
        S.push(make_pair(i,h));
    }

return 0;
}