[백준/boj] 2493번: 탑 | C++

오른쪽부터 반복문을 도는 형식 & 반복 횟수를 줄여야 함(의미없는 연산을 하지 않도록)-> 스택을 이용

 

목차

1. 문제풀이 핵심

2. 문제풀이 코드

2-1. 로직 설명

3. 문제풀이에 사용된 함수

3-1. stack<pair<자료형,자료형>>

 

---

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

2493번: 탑

문제풀이 핵심

이중 for 문을 사용하게 되면 시간복잡도가 O(n^2) 이 되며 1.5초를 넘어 시간초과가 뜨게 된다.

따라서 O(n)의 시간 복잡도를 가진 로직을 생각해내는것이 핵심이다.

 

O(n)의 시간복잡도를 충족하기 위해서는 문제에서 주어지는 탑 높이 입력을 다 받은 후에 후처리를 하는 것이 아닌

높이를 입력 받는 동시에 높이 비교 연산을 진행해야겠다는 생각을 하는게 문제풀이의 핵심이었다.

---

문제풀이 코드

#include<iostream>
#include<stack>

using namespace std;

stack<int> topList;
stack<int> topNum;
int n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >>n;

    int f;
    cin >>f;

    topList.push(f);
    topNum.push(1);
    cout << '0' <<' ';

    for(int i =1;i<n;i++){
        int newTop;

        cin >> newTop;

        //오른쪽(새로 들어온 값)이 왼쪽(top)보다 큰 경우
        while(!topList.empty()&& newTop >= topList.top()){
            //기존 top 없앰
            topList.pop();
            topNum.pop();
        }
        
        if(topNum.empty()){
            cout << '0'<<' ';
        }else{
            cout << topNum.top()<<' ';
        }

        topNum.push(i+1);
        topList.push(newTop);
    }
    return 0;
}

---

로직 설명

탑 높이 입력에서 먼저 입력받은 값보다 더 큰 값을 나중에 입력받으면 먼저 입력받은 값은 더이상 사용되지 않는 값이 된다. 

문제 자체가 오른쪽부터 본인보다 큰 가장 가까운 수를 찾는 문제이기 때문이다. 

 

따라서 탑의 높이를 입력받으며 기존의 topList 스택의 top()인 요소와 새로 입력받은 요소중에 새로 입력받은 것이 더 큰 값이면 기존의 topList 에 존재하는 값과 그 탑의 순서를 의미하는 topNum의 top()값을 pop()하여 삭제한다. 이과정은 topList 가 빈 배열이 되거나(왼쪽 끝까지 돌았는데 본인보다 높은 탑이 없는 경우) topList에서 새로 입력받은 값보다 큰 값을 찾을때까지 반복된다. (위 코드의 while문)

 

while 문을 탈출 했을 때 그 이유가 topList.empty()라면 입력받은 탑 기준 왼쪽에 본인보다 높은 탑이 없는것이기에 0을 출력해주고 그게 아니라면 본인보다 높은 탑을 찾은것이므로 topNum()의 top()값을 출력해준다. 

 

그 후 topNum과 topList에 현재 입력받은 값을 넣어준다. 

---

 

문제풀이에 사용된 함수

STL stack 을 사용했다

stack 라이브러리에서 push(),top(),pop(),empty() 함수를 사용하였다

---

 

stack <pair < 자료형,자료형>>

스택에 두개의 값을 묶어서 저장하는 방식이다. 

 

이 문제에서 탑의 높이와 탑의 순서를 같이 저장해야 하는 경우에 사용하면 좋다.

이걸 몰라서 나는 스택 두개를 사용했는데 이걸 이용하면 스택하나로 높이와 순서를 모두 저장할 수 있고

push, pop 등의 관리도 한번에 처리할 수 있기 때문에 로직상의 간결함을 잡고 공간복잡도 줄일 수 있는 방법이다.

 

---

 

마무리

시간복잡도를 생각하며 로직을 짜는게 까다로운 문제였다..