[백준] 17298번: 오큰수

여기를 클릭하면 문제를 볼 수 있습니다.

📕 문제 설명

📕 문제 풀이

제가 해결한 방법은 다음과 같습니다.

제가 문제를 해결할 때 초점에 둔 것은 오큰수의 정의입니다.
문제에서는 오큰수를

$A_i$

와 같이 정의하고 있습니다.

그렇다면 오큰수의 정의에 따라 $A_i$

하지만 위의 경우와는 다르게 오큰수를 바로 찾지 못하는 상황이 있습니다. 아니, 더 많을 것입니다.

📗 예시1

문제에서 주어진 예시로 설명해보겠습니다.

위의 예제의 오큰수를 찾아보겠습니다.

위에서 언급했듯이 첫번째로 오큰수를 찾는 방법은 $A_{i+1}$

그러면 처음에는 3과 5를 비교하겠죠. 5는 3보다 크므로 3의 오큰수가 됩니다. 물론 다른 원소들은 볼 것도 없습니다. 5가 3보다 크면서 가장 왼쪽에 있기 때문입니다.

이제 5와 2를 비교합니다. 2는 5의 오큰수가 될 수 없으므로 이 단계에서는 5의 오큰수를 찾지 못하고 넘어갑니다.

다음으로는 2와 7을 비교합니다. 7은 2의 오큰수가 2의 오큰수 자리에 7을 넣습니다.

여기서 아까 오큰수를 찾지 못했던 5를 생각해봅시다. 2의 오큰수인 7은 5의 오큰수도 됩니다. 그러므로 5의 오큰수로 7을 추가합니다.

이 상황을 일반화 해봅시다.

오큰수를 찾는 첫번째 방법은 위에서 소개했듯이 $A_i$

즉,
$A_i < A_{i+1}$

이와 반대로
$A_i ≥ A_{i+1}$

이 상태에서 언젠가 $A_i < A_{i+1}$

이런 흐름을 봤을 때 오큰수를 찾지 못한 원소들을 하나씩 저장했다가 후에 하나씩 꺼내어 보기에 적절한 자료구조는 Stack이 되겠습니다.

위의 예를 마저 끝내고 일반화를 한 상태에서 다른 예를 하나 더 들어보겠습니다.

7은 마지막 원소이므로 오큰수가 될 수 있는 원소가 존재하지 않으므로 문제의 정의에 따라 -1을 출력 배열에 추가해줍니다.

이제 문제 해결 일반화를 정리하고 다음 예시로 넘어가겠습니다.

📗 문제 해결 일반화

1. 오큰수를 찾는 기본적인 방법은 $A_i$
2. $A_i < A_{i+1}$
3. $A_i ≥ A_{i+1}$
4. $A_i < A_{i+1}$
5. $stack.top() < A_{i+1}$
6. 마지막 원소까지 비교했을 때도 오큰수를 찾지 못한 원소들의 오큰수는 -1이다.

📗 예시2

위와 같이 예시가 주어졌을 때 각 원소들의 오큰수를 문제 해결 일반화를 적용하여 찾아보겠습니다.

1. 오큰수를 찾는 기본적인 방법은 $A_i$

을 적용하여 풀이하면

처음으로는 9와 5를 비교하게 됩니다.
9는 5보다 작으므로

3. $A_i ≥ A_{i+1}$

9를 스택에 저장합니다.

그런데 여기서 잠깐 생각해봅시다. 나중에 $A_i < A_{i+1}$

이제 5와 4를 비교합니다. 4는 5보다 작으므로 오큰수를 찾지 못했으므로 스택에 넣어줍니다.

다음으로는 4와 8은 비교합니다.

2. $A_i < A_{i+1}$

에 따라 8은 4의 오큰수가 되므로 출력 배열에 추가하면 됩니다.

4. $A_i < A_{i+1}$

스택에 원소들이 있기 때문에 하나씩 꺼내어 8이 그 원소의 오큰수가 되는지 비교 합니다.

$5 < 8$

5. $stack.top() < A_{i+1}$

에 따라 8을 5의 오큰수가 됩니다. 그리고 5의 오큰수를 찾았으므로 5를 스택에서 꺼내줍니다.

9는 8보다 크므로 8은 9의 오큰수가 될 수 없습니다. 나중에 다시 $A_i < A_{i+1}$

8은 마지막 원소이므로 오큰수가 존재하지 않으므로 오큰수를 -1 처리 해줍니다.

6. 마지막 원소까지 비교했을 때도 오큰수를 찾지 못한 원소들의 오큰수는 -1이다.

마지막 원소까지 비교했음에도 불구하고 9의 오큰수를 찾지 못했으므로 -1처리 합니다.

📕 Code

이제 이를 코드로 나타내봅시다.

#include <iostream>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

vector<int> nums(1'000'001);
vector<int> answer(1'000'001);

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;  cin >> n;
    for(int i=0; i<n; i++)
        cin >> nums[i];

    stack<pair<int, int>> st;	// Ai와 idx를 저장할 스택
    for(int i=0; i<n-1; i++)
    {
        if(nums[i] < nums[i+1])	// A[i] < A[i+1] 이면 오큰수를 찾음
        {
            answer[i] = nums[i+1];	// 오큰수 저장
            while(!st.empty() && st.top().first < nums[i+1])
            {		// 스택에 저장된 오큰수를 찾지 못한 원소들을 하나씩 꺼내어 
            		// A[i+1] 이 오큰수가 되는 지 비교
                answer[st.top().second] = nums[i+1];	// 오큰수가 된다면 추가!
                st.pop();	// 오큰수를 찾았으므로 pop!
            }
        }
        else
            st.push(make_pair(nums[i], i));	// A[i] >= A[i+1] 이면 
            					// 오큰 수를 찾지 못했으므로 
 		                                // 스택에 저장!
    }
    st.push(make_pair(nums[n-1], n-1));		// 마지막 원소는 오큰수가 없으므로 스택에 저장

    while(!st.empty())		// 마지막 원소까지 비교했음에도 불구하고 
    				// 오큰수를 찾지 못한 원소들은
    {
        answer[st.top().second] = -1;	// -1 처리
        st.pop();
    }

    for(int i=0; i<n; i++)
        cout << answer[i] << ' ';

    return 0;
}

감사합니다.

📕 후기

역시 같은 자료구조를 사용하더라도 그 자료구조를 어떻게 사용할 지 다방면에서 볼 필요가 있다...
한 방법에만 집중하지 않고 다양한 각도에서 풀이법을 생각해보자!