[BOJ 2493] 탑

2493번: 탑

문제 분석

• 오큰수와 매우 유사하다. ( https://genius00hwan.tistory.com/68 )
• 시간제한이 0.5초 더 널널하다
• 다뤄야 하는 정수의 수도 오큰수 보다 적다.
• 오큰수 방식으로 풀면 시간초과는 안나겠다.
• 각 원소의 값보다 왼쪽에 있는 수에 대한 문제이다.(오큰수는 오른쪽)
• 오큰수는 원소의 값을 가리킨다면, 이 문제는 원소의 인덱스를 가리킨다.

[BOJ 17298] 오큰수

풀이 방식

• 왼쪽에 있는 수 부터 처리한다.
• 나머지는 오큰수와 같은 논리로 푼다.
• 스택에 원소의 인덱스도 함께 저장한다.

vector<pair<int, int>> twr; //(탑의 높이, 수신한 탑의 번호)
stack<pair<int, int>> rcp; //(탑의 높이, 탑의 번호)
int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    twr.emplace_back(0, 0);
    //가장 왼쪽의 있는 탑의 번호는 1번이므로 0번 인덱스에 의미없는 값을 넣어준다.
    while (n--) {
        int x;
        cin >> x;
        twr.emplace_back(x, 0);
    }
    for (int i = 1; i < twr.size(); i++) {
        while (!rcp.empty()) {
            if (rcp.top().first > twr[i].first) {
                twr[i].second = rcp.top().second;
                break;
            } else {
                rcp.pop();
            }
        }
        rcp.push({twr[i].first, i});//스택에 저장할때 인덱스도 함께 저장한다.
    }
    for (int i = 1; i < twr.size(); i++) {
        cout << twr[i].second << " ";
    }
    return 0;
}

느낀 점

• 오큰수 유형의 문제를 벌써 세번째 풀었다. 이 유형의 문제는 꽤 중요하다는 생각이 든다.
• 주기적으로 오큰수 문제를 복습하고 비슷한 유형의 문제를 찾아 풀어봐야 겠다.