[자료구조] 백준 17299번 오등큰수(C++)

 

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

 

해당 문제를 풀기전에 아직 이전 문제인 오큰수를 안풀어봤다면 꼭 풀어보고 오거나, 해설이라도 보고오는 것을 추천한다

 

https://lee-soo.tistory.com/6

[자료구조] 백준 17298번 오큰수(C++)

 

 

오등큰수란

예시에서 보여준 1 1 2 3 4 2 1 의 경우

숫자 1의 횟수 = 3

숫자 2의 횟수 = 2

숫자 3의 횟수 = 1

숫자 4의 횟수 = 1

 

맨 처음 원소부터 시작한다면

0번째 인덱스인 1은 횟수가 3이고

그 오른쪽에는 자기자신을 제외한 횟수가 3번이상 나온 숫자가 없다!

그렇다면 -1이고

2번째 인덱스인 1 1 2 즉 2를 가보자

2의 경우 횟수가 2이고 오른쪽에서 2보다 횟수가 많이 나온건 1이 있다

그래서 2번째 인덱스에는 1이 들어간다

 

그럼 더 나아가 4로 가보자

4의 오른쪽에는 2 1 둘다 4보다 횟수가 많지만

가장 왼쪽에 있는것을 고르라 했으니 이것은 2가된다.

뭔가 오큰수랑 비슷한 개념이다.

 

이미 오큰수에서 무작정 모든 경우의 수를 도는건 안된다는것을 알았으니 같은 방법으로 스택을 사용하여 보자

 

int c;

    cin >> c;

    int arr[c];

    int result[c]; // 오큰수를 저장할 배열

    stack<int> st;

    for (int i = 0; i < c; i++) // 입력받기

    {

        cin >> arr[i];

    }

    for (int i = c - 1; i >= 0; i--) // 뒤에서부터 오큰수 찾기

    {

        // 스택에서 현재 숫자보다 작거나 같은 숫자는 제거

        while (!st.empty() && st.top() <= arr[i])

        {

            st.pop();

        }

        // 스택이 비어 있으면 오큰수가 없다는 뜻

        if (st.empty())

        {

            result[i] = -1;

        }

        else

        {

            result[i] = st.top(); // 스택의 맨 위가 오큰수

        }

        st.push(arr[i]); // 현재 숫자를 스택에 넣음

    }

    for (int i = 0; i < c; i++)

    {

        cout << result[i] << " ";

    }

    cout << "\n";

    return 0;

먼저 이 코드는 오큰수에서 사용한 코드이다.

 

이 코드에서 스택은 숫자를 넣었지만, 우리는 숫자대신 "횟수"를 사용할 것이다

그렇다면 비교문안에는 횟수가 들어가야 할 것 아닌가?

 

그럼 횟수를 저장하는 배열과, 실제 들어간 숫자를 저장하는 배열 두가지를 만들어야 될 것이다.

 

 

가장 첫번째 중복문을 지나 while문에 들어갈 때,

   while (!st.empty() && st.top() <= arr[i])

가 있다.

 

우리가 

필자가 지금까지 코테를 공부했을 때,

복잡한 과정을 거치지 않고 "횟수"를 저장하기 위해선

배열의 인덱스를 통해 저장하는것이 편했다.

 

자 그럼 어떻게 정의를 할까?

 

int arr_1[100001]={0};

int arr_2[n];

 

으로 하면 될 것이다

arr_1에는 당연히 해당 인덱스에 해당하는 값들이 몇번 나왔는지

arr_2에는 실제 입력된 배열을 저장하는 것

 

아래에 실제 result에 값을 넣을 때는 st.top()을 넣는다

그렇다는 것은 스택의 안에는 "횟수"가아닌 "값"이 들어가야 한다는 것이므로

 

처음 while문을 통한 조건문은

 

!empty && arr_1[st.top] <= arr_1[arr_2[i]]일 것이다.

왜냐? 자신보다 오른쪽에 있는 것들 중에 더 커야하니까 작은것들은 패스하기 위해서다

 

그럼 아래는 간단하다

오큰수와같이 스택이 비어있다면 자신보다 큰 값이 없으므로 -1 

있다면 자신을 기준으로 오른쪽에있으면서 가장 왼쪽에있는 st.top을 결과로 가져오면 된다.

 

코드를 짜보자

 

#include <iostream>

#include <stack>

using namespace std;

int arr_1[1000001] = {0};

int main()

{

    int c;

    cin >> c;

    int arr_2[c];

    int result[c];

    stack<int> st;

    for (int i = 0; i < c; i++)

    {

        int temp;

        cin >> temp;

        arr_1[temp]++;

        arr_2[i] = temp;

    }

    // arr_1 = 입력값의 갯수 , arr_2=해당 값

    for (int i = c - 1; i >= 0; i--)

    {

        while (!st.empty() && arr_1[arr_2[i]] >= arr_1[st.top()])

            st.pop();

        if (st.empty())

            result[i] = -1;

        else

            result[i] = st.top();

        st.push(arr_2[i]);

    }

    for (int i = 0; i < c; i++)

    {

        cout << result[i] << " ";

    }d

    cout << "\n";

}