boj 17298 오큰수 와 boj 2493 탑 의 유사성에 관하여. 그리고 boj 6198 옥상 정원 꾸미기 와의 차이점

boj 17298번 문제 오큰수의 경우 boj 2493 탑 문제와 배우 유사한 형태를 가지는데, 이때에 차이점은 문제에서 탑의 경우는 왼쪽으로 바라보고, 오큰수는 오른쪽을 바라보고 자신보다 크거나 같은 숫자가 나타날때까지 확인을 하고 그 후에 그에 해당하는 경우 해당 숫자 혹은 해당 숫자의 인덱스를 출력하는데 있다. 

그런데 이때에 차이점이 방향성인데, 탑의 경우 가장 대표적인 형태라고 생각할 수 있을것 같고, 그대로 바로 입력된 수들과 비교하면서 왼쪽으로 레이저를 쏜다는 개념이 스택에 수를 넣고 그대로 바로 스택에 쌓인 수들 자체로 비교를 한다는 것이기 때문에 꼬이지 않고 그대로 입력되는 순서와 스택을 사용하면 된다

 

그런데 오큰수 문제의 경우는 오른쪽으로 바라보는 형태로 되기 떄문에 수가 나오는 순서와, 그 수를 담는 순서에서 스택을 활용할때 사용할 수 있는 체크 방법과는 정 반대로 수를 바라보게 된다. 

그래서 이 문제를 해결하기 위해서는 오큰수 문제의 입력을 탑 형태처럼 만들어서 동일한 해법으로 문제를 해결하기 위해서 오큰수에서 제시해주는 순서들을 따로 담아두었다가, 역순으로 스택을 다루는 형태로 만들면 탑의 문제형태로 동일하게 만들 수 있고, 그렇기 때문에 그 형태에서 스택을 활용해서 문제를 해결할 수 있게 된다. 

이때에 추가적으로 예외사항인 자신보다 큰 숫자가 없을때는 -1 을 넣어주면 되는것이다. 

 

그리고 출력하는데 있어서도 반복문 내에서 숫자를 역순으로 담기 위해서 int i=n-1; i>=0; i--

형태로 수를 다루기 때문에, 탑 문제처럼 그대로 바로 원하는 녀석들을 stirng에 담아버린다던지, 혹은 바로 출력을 해버리면 원하는 결과물과는 정 반대로 출력이 되버리기 때문에,

(예를들어 이런 코드)

#include <bits/stdc++.h>
using namespace std;

const int mx=1'000'005;

int a[mx];
int ans[mx];

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

    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    stack<int> s;
    for(int i=n-1; i>=0; i--){
        while(!s.empty() && s.top()<=a[i])
            s.pop();
        if(s.empty())
            // ans[i]=-1;
            cout<<"-1 ";
        else
            // ans[i]=s.top();
            cout<<s.top()<<' ';
        s.push(a[i]);
    }
    // for(int i=0; i<n; i++)
    //     cout<<ans[i]<<' ';  
}

 

다시 제대로된 순서로 출력을 해주기 위해서 정답을 담아줄 배열을 만들어서 배열에 담고, 

그걸 원래의 순서로 다시 출력해주어야 한다. 

그래서 

#include <bits/stdc++.h>
using namespace std;

const int mx=1'000'005;

int a[mx];
int ans[mx];

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

    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    stack<int> s;
    for(int i=n-1; i>=0; i--){
        while(!s.empty() && s.top()<=a[i])
            s.pop();
        if(s.empty())
            ans[i]=-1;
            // cout<<"-1 ";
        else
            ans[i]=s.top();
            // cout<<s.top()<<' ';
        s.push(a[i]);
    }
    for(int i=0; i<n; i++)
        cout<<ans[i]<<' ';  
}

이와같은 형태로 배열을 두개 두어서 처음에 입력받는 배열, 역순으로 출력되는 배열을 담을 배열을 만들고, 

역순으로 출력되는 배열을 담을 배열을 다시 정순으로 출력하면서 원하는 답을 출력하면 된다. 

 

이때에 6198 옥상 정원 가꾸기 문제와의 차이점을 생각해보면, 지금까지 풀어본 문제들은 대부분 수 하나를 만나면 그와 관련된 내용을 출력하거나 하는 형태에서는 그냥 바로 stack을 사용해서 풀면 되었고, 그렇기 때문에 바라보는 방향, 혹은 레이저를 쏘는 방향등의 형태로 문제가 나온다면 그렇게 풀면 되겠고, 그것이 아니라 여러개를 관찰한다던가 하는 형태는 stack을 통해서 하나만 딱 만났을때의 형태로 해결되는 문제가 아니기 때문에 이때에는 문제의 예제에서 나타내는 형태로 출력이 되는것이 아닌 형태의 문제, 예를들어 6198 옥상 정원 꾸미기 형태의 문제가 되는 것이다. 둘의 차이점에 대해서 잘 인식하도록 하자. 

 

유사성은 결국

 

탑과 오큰수   ||   옥상 정원 꾸미기

 

형태로 갈릴 것이다.