JArchive 프로그래밍 일기

문제

탑 백준 2493

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;
​
int main() {
​
    int K, height;
    stack<pair<int,int> > s; // <인덱스, 높이>를 저장한 스택
​
    scanf("%d", &K);
​
    for(int i = 1; i <= K; i++){
​
        scanf("%d", &height);
​
        while(!s.empty()){
            if(s.top().second > height){ // 수신탑 발견한건지 검사
                printf("%d ", s.top().first); // 발견한 수신탑의 인덱스 출력 
                break;
            }
            s.pop(); //수신탑 찾을 때 까지 꺼낸다 
        }
​
        if(s.empty()){ // 수신탑을 못찾은 경우 0
            printf("0 ");
        }
        s.push(make_pair(i, height)); // 탑의 인덱스와 높이를 저장 
    }
​
    return 0;
}

리뷰

헷갈렸는데. 검색을 통해 탑의 인덱스를 저장해야 된다는 것을 알고 코드를 고쳤다.

스택에 (인덱스, 탑 높이) 쌍으로 par를 저장한다.

6 입력

- 스택이 비었으니까 0을 출력하고. 자기자신 (인덱스 1, 높이6)을 스택에 push

현재 스택에 (1, 6) 들어있음

9 입력

- 자신보다 높은 높이가 나올때 까지 pop한다. 6이 제거된다. 스택이 비게된다.

그리고 자기자신 (인덱스 2, 높이9)를 스택에 push

현재 스택에 (2, 9)들어있음

5 입력

- 자신보다 높은 높이를 찾는데, 9가 들어있다.

9의 인덱스인 2를 출력. 그리고 자기자신 (인덱스 3, 높이 5)를 스택에 push

현재 스택에 (2,9), (3,5) 가 들어있음. top은 방금 넣은 5다.

7 입력

- 자신보다 높은 높이 나올때 까지 pop한다. 5가 제거되고 9를 발견하게 된다.

9의 인덱스인 2를 출력. 그리고 자기자신 (인덱스 4, 높이 7) 을 스택에 push

현재 스택에 (2,9),(4,7) 이 들어있음. top은 방금 넣은 7이다.

4입력

- 자신보다 높은 높이인 7이 현재 스택의 top이다.

7의 인덱스인 4를 출력. 그리고 자기자신 (인덱스 5, 높이4)를 스택에 push

현재 스택에 (2,9),(4,7), (5,4) 이 들어있음.