[C++] BOJ 2493 / stack 과 pair의 사용

 

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

2493번: 탑

스택을 사용하는 문제를 풀던 중 만난 문제였다.

PS에 대한 경험이 적다보니, 손 가는 대로 코드를 짰고 그 결과 시간초과가 발생하였다.

처음 구현했던 방법은 Stack 3개를 써서 구현한 방식이었다.

 

시간을 단축하기 위해서 타워의 높이를 일괄적으로 스택에 넣고 POP 하며 계산하는 것이 아닌, 높이를 하나씩 push 받으면서 계산을 해야한다는 생각이 들었다.

첫 번째 시도에서는 놓쳤던 이 문제에서의 Key Point는 "높이가 작아서 POP한 탑을 저장했다가 다시 PUSH하지 않아도 된다": 이다. 이를 놓쳐서 처음에 스택 세개를 사용해서 구현했던 것이다.

 

자세히 설명하자면, 예를 들어 탑의 높이가 6 9 5 7 4 라고 했을 때, 레이저가 왼쪽으로만 나가고, 레이저를 쏘는 탑 기준 왼쪽에 있는 탑 중 처음 만나는 높은 탑만 찾으면 되기 때문이다.

탑이 6 9 5 나, 9 5 나 차이가 없다. 다른 경우인 4 6 5 1 이나 5 1 이나 차이가 없다.

 

구현 코드는 아래와 같다.

 

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    int max = 100000001;
    stack<pair<int, int>> stk;
    cin >> n;
    stk.push({max, 0});
    for(int i = 1; i <= n ; i++) {
        cin >> k;
        while(stk.top().first < k) {
            stk.pop();
        }
        cout << stk.top().second << " ";
        stk.push({k, i});
    }
    return 0;
}

 

stack은 C++ STL로 제공되기 때문에 문제가 없었지만, 문제에서 요구하는 것은 "몇 번째 탑" 이었기 때문에 적합한 자료구조를 찾던 중 "pair"를 알게되었다.

 

pair는 STL에서 쌍으로 표현되는 자료형을 위해 제공되는 컨테이너이며, <utility> 헤더에 존재한다.

 

pair의 기본 생성 방법은

pair<(type 1), (type 2)> (이름); 이다.

 

pair를 할당하는 방법에는 두 가지 방식이 있다.

첫 번째 방식은 make_pair() 함수를 이용한 방법이고,

두 번째 방식은 {}를 이용한 방법이다. (해당 문제를 풀 때 사용한 방식이다.)

 

pair 값을 참조하는 방법은 .first와 .second를 사용한다.

 

이번 문제를 통해, 떠오르는 대로 코드를 짜기 보다는, 제시해주는 테스트케이스를 더 작게 쪼개어 패턴이나 중요 특징을 찾는 것이 중요하다는 것을 깨닫게 되었다.

 

참고링크 :

pair 사용법

https://hellominchan.tistory.com/199

[C++] pair 사용법