[BOJ] 2493: 탑

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

 

 

 

 

 

: 처음 작성한 코드

#include <bits/stdc++.h>
using namespace std;
stack<int> tower;
vector<int> result;
int n, k;
int pos, max_k;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> k;
    if (!tower.empty()) {
      if (tower.top() > k)
        pos = tower.size();
      else {
        if (k > max_k) {
          max_k = k;
          pos = 0;
        }
      }
    }
    tower.push(k);
    result.push_back(pos);
  }
  for (int num : result) cout << num << ' ';
}

나는 스택 pop연산을 사용하지 않고 풀이하려고 했다.

입력을 스택에 쌓을 때마다 스택의 top과 k를 비교한다.

top이 더 크다면 pos를 스택 사이즈로 업데이트하고 k를 스택에 push한다.

이때 pos가 바로 레이저의 수신을 받는 송신탑의 위치다.

 

만약 top이 k보다 작다면 pos를 업데이트 하지 않는다.

이때 k가 스택에 있는 탑 중 가장 높은 탑이라면 pos를 0으로 업데이트한다.

 

위 코드로 테스트 케이스를 통과하는 것도 확인했고 내가 만든 다른 테스트 케이스도 대부분 통과하는 것을 확인했지만,

제출 결과는 실패였다.

반례를 찾아내면 코드를 수정할 수 있을 것 같은데 아직 찾지 못해서 다른 방법으로 접근했다. 

 

 

 

이 문제는 기준이 되는 탑보다 높이가 작은 탑들은 모두 무시하고 더 큰 탑만 레이저를 수신한다.

따라서 현재 입력이 top보다 크다면 스택 pop을 하고, 작다면 스택 top에 있는 탑의 위치를 출력하면 된다고 생각했다.

 

스택에 탑의 높이뿐만 아니라 위치를 어떻게 하면 함께 넣을 수 있을지 생각해봤다.

 다른 분들의 코드를 보니 나와 비슷한 생각을 하신 분들이 많이 계셨고, 그분들은 pair를 사용해서 나의 고민을 해결했다.

 

pair는 다른 데이터 두 개를 하나로 묶어서 사용할 수 있는 STL이다.

pair<int, int>의 형식으로 선언할 수 있고 난 스택에 넣어 사용해야 하기 때문에 stack<pair<int, int>> tower; 로 선언했다.

 

pair에서 각 두 데이터는 first와 second로 접근할 수 있는데

나는 first는 탑의 위치, second는 탑의 높이로 사용했다.

 

다른 분들의 코드를 참고하면서 새롭게 짠 코드는 아래와 같다.

 

 

 

: 나중에 작성한 코드

#include <bits/stdc++.h>
using namespace std;
stack<pair<int, int>> tower;
vector<int> result;
int n, h, max_k;
int pos;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  tower.push({0, 100000001});
  for (int i = 1; i <= n; i++) {
    cin >> h;
    while (tower.top().second < h) tower.pop();
    cout << tower.top().first << ' ';
    tower.push({i, h});
  }
  cout << '\n';
}