백준(C++) 17298 [오큰수], 17299[오등큰수]

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

오큰수 17298

접근방법

오큰수는 스택을 이용하여 푸는 문제이다. 문제를 보면 배열에 있는 원소의 오른쪽에 원소보다 가장 더 큰수를 찾으면 그 수 를 출력 한다. 만약 그 수가 없으면 -1를 출력한다. 이는 스택 이용하면 쉽다. 입력을 통해 배열안에 수를 넣고, 비교문을 통과해 정답 배열안에 정답을 넣는다.

이때 비교문을 스택으로 쓴다.

예를들어 조건을 살펴보면 

입력 3,5,2,7일때 비교문에 들어올때 입력 원소 방향은 맨 오른쪽부터 왼쪽으로 간다. 여기서 스택이 비어있으면 스택에 현재 수를 push한다.

만약 스택이 비어있지 않고, 입력배열의 현재수가 스택의 top 수보다 크거나 같으면 스택을 계속 pop한다.

이 모든 조건이 아니라면 -1를 정답배열 안에 넣는다.

뭔가 예를 들으니 더 이상해졌지만 이를 잘 다듬어 만들어내는게 이 문제의 핵심같다. 그렇게 어렵지는 않은 문제다.

 

코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<stack>

using namespace std;

int in_m[1000001]; //입력 배열
int out_m[1000001]; //정답 배열
stack<int> s; //비교할때 쓰는 스택문

int main(void)
{
    cin.tie(0);
    int N;
    cin >> N;
    for(int a=0;a<N;a++)
    {
        cin >> in_m[a];
    }

    for(int a=N-1;a>=0;a--)
    {
        while(!s.empty()&&in_m[a] >= s.top())
        s.pop();

        if(s.empty())out_m[a] = -1;
        else out_m[a] = s.top();

        s.push(in_m[a]);
    }

    for(int a=0;a<N;a++)
    {
        cout << out_m[a] << " ";
    }
    return 0;

}

 

여기서 오등큰수를 살펴보자

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

 

오등큰수는 오큰수와 비슷하지만 이를 빈도수로 바꾼문제이다.

그렇다면? 빈도수 배열을 하나더 추가하면된다. 오큰수만 알면 바로 해결할수있는 연계 문제이다.

빈도수 배열을 이용하여 입력시 빈도수를 빈도수 배열에 입력한다.

그리고 이를 비교문을 통해 비교하면 끝이다. 비교문은 빈도수 배열로만 바꾸고 오큰수와 같은 원리이다.

 

다음은 코드이다.

#include<iostream>
#include<algorithm>
#include<stack>

using namespace std;

int in_m[1000001]; //입력 배열
int num_m[1000001]; //빈도수 배열
int out_m[1000001]; //정답 배열
stack<int> s; //비교할때 쓰는 스택문

int main(void)
{
    cin.tie(0);
    int N;
    cin >> N;
    for(int a=0;a<N;a++)
    {
        cin >> in_m[a];
        num_m[in_m[a]]++;
    }

    for(int a=N-1;a>=0;a--)
    {
        while(!s.empty()&&num_m[in_m[a]] >= num_m[s.top()])
        s.pop();

        if(s.empty())out_m[a] = -1;
        else out_m[a] = s.top();

        s.push(in_m[a]);
    }

    for(int a=0;a<N;a++)
    {
        cout << out_m[a] << " ";
    }
    return 0;

}

 

오큰수 조건 정리하는게 조금 해맸지만 쉬운 문제였다.