[백준] 1083번_소트 C++

07 Mar 2023 in Study on Coding Test

정렬과 그리디 알고리즘을 활용하는 문제

정답제출코드

#include <iostream>
#include <vector>

using namespace std;

int m_min(int a, int b)
{
    if (a > b)
        return b;
    else
        return a;
}

int main()
{
    int N, S;
    vector<int> numbers;

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int _input;
        cin >> _input;

        numbers.push_back(_input);
    }

    cin >> S;

    for (int i = 0; i < N; ++i)
    {
        // 카운트가 0이면 순환할 것도 없이 바로 break
        if (S <= 0)
            break;

        // 초기 max값 기준을 잡아줌.
        int max = numbers[i];
        int index = i;
        
        // 큰 수가 멀리 있다면 얼마나 더 멀리 있는 수를 끌어올지 범위가 더 적은 수를 파악해둔다.
        int miner = m_min(N, i+S+1);


        // 가장 큰 수의 위치를 파악한다.
        for (int j = i+1; j < miner; ++j)
        {
            if (max < numbers[j])
            {
                max = numbers[j];
                index = j;
            }
        }

        // 가장 큰수가 앞으로 오는 과정까지 카운트를 소모했을 것.
        S = S - (index - i);

        // 큰 수가 지나가는 과정에서 바뀐 자리 정리
        // ex: 1 2 3 4 5 -> 5 1 2 3 4 
        for (int j = index; j > i; --j)
        {
            numbers[j] = numbers[j-1];
        }

        // 앞쪽에다가 구한 큰 수를 순서대로 배치.
        numbers[i] = max;
    }


    for (int i = 0; i < N; ++i)
        cout << numbers[i] << ' ';

    return 0;
}

30분 고민하다가 참고 링크를 활용하여 문제를 풀었다.

문제를 푸는 과정에서 가장 큰 값을 앞으로 끌어오는데 카운트를 얼마나 소모하는지 구현하는 과정이 까다로웠다.

오답제출코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, S;
    vector<int> numbers;

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int _input;
        cin >> _input;

        numbers.push_back(_input);
    }

    cin >> S;
    
    int count = 0;

    for (int i = 0; i < N; ++i)
    {
        if (S == 0)
            break;
        
        for (int j = 0; j < N-1; ++j)
        {
            if (numbers[j] < numbers[j+1] && count < S)
            {
                // swap
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
                count++;
            }
        }
    }

    for (int i = 0; i < N; ++i)
        cout << numbers[i] << ' ';

    return 0;
}

찜찜하게 테스트케이스 3개가 모두 맞아서 설마..? 하는 마음으로 제출해보았지만 역시 결과는 틀렸다.

잘 생각해보니 아래와 같은 반례가 있네.

반례

5
1 2 3 4 5
4

// 원하는 결과 : 5 1 2 3 4
// 출력 결과 : 2 3 4 5 1

S가 충분히 크다면 가능한 가장 큰 수를 앞으로 끌어오는 과정이 필요했다.