백준 2493 탑 [C++]

작성일 | In |

Problem : 탑

유형 : 스택

문제 해석

  • 각각의 탑에서 발사한 레이저를 어느 탑에서 수신하는지 찾아내라.

해결전략

  • -> 방향으로 탑이 주어진다고 생각했을때, 이전보다 더 높은 탑이 등장하면, 이전의 탑은 의미가 없어진다.
    • 이후에 등장한 더 높은탑이 모든 레이저를 다 수신해버리기 때문이다.
    • 인접한것에 관심을 가지므로 스택 을 통해 O(N) 으로 해결한다.

주의할점

  • 출력해야 하는것은 탑의 높이 가 아니라 탑의 번호 이다.

구현

  • pair 자료형을 이용해 { 높이, 번호 } 를 저장한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define pii pair<int,int>
#define height first
#define number second

using namespace std;

void solve() {
    stack<pii> tower;
    int n;  cin >> n;
    int towerHeight;
    for(int i = 1; i <= n; ++i) {
        cin >> towerHeight;
		while (!tower.empty()) {
			if (tower.top().height <= towerHeight) tower.pop();
            else {
                cout << tower.top().number << " ";
                break;
            }
		}
        if (tower.empty()) cout << 0 << " ";

        tower.push({ towerHeight, i });
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 항상 이야하는거지만, 출력조건, 입력조건을 확실히보자.
    • 최초의 코드는 높이를 출력했다.