I. Out of Place

Editor: 김정현 (powergee)

문제 상황 설명

소들을 키에 따라 오름차순으로 정렬해 두었다가 Bessie가 자리를 이탈해 멋대로 다른 자리에 끼어들었습니다. 이들을 다시 오름차순으로 정렬하기 위해 한 쌍의 소의 위치를 바꾸는 작업을 최소 몇번 해야 할까요?

문제 풀이

Bessie(자리가 옳지 않은 소)를 옳은 위치를 향하는 방향으로 이웃한 소와 위치를 바꾸며 정렬해야 합니다. 여기서 이웃한 소만 생각하는 이유는 만약 이웃하지 않은 소와 위치를 바꾸게 된다면 위치가 옳지 않은 소가 한마리 더 생기기 때문입니다. 단, 키가 같은 여러 마리의 소와 자리를 바꿔야 한다면 그 집단의 마지막 소와만 자리를 교체함으로써 한번에 소를 이동시킬 수 있습니다. 이것은 같은 키의 소는 중복해서 배열에 입력하지 않고 단 한번만 입력받는 방법으로 구현할 수 있습니다.

소들을 이동시키는 과정은 거품정렬(Bubble Sort)이나 선택정렬(Insertion Sort)의 원리를 이용할 수 있습니다.

소스 코드 (C++)

Out of Place.cpp

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> seq;

int CountByBubble()
{
    int count = 0;
    std::vector<int> arr(seq.begin(), seq.end());

    for (int i = 0; i < arr.size(); ++i)
    {
        for (int j = 0; j <= (signed)arr.size() - 2 - i; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                std::swap(arr[j], arr[j + 1]);
                ++count;
            }
        }
    }

    return count;
}

int main()
{
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; ++i)
    {
        int input;
        scanf("%d", &input);

        if (seq.empty() || seq.back() != input)
            seq.push_back(input);
    }

    if (N == 2)
    {
        if (seq.front() <= seq.back())
            printf("0");
        else printf("1");
    }
    else
    {
        printf("%d", CountByBubble());
    }

    return 0;
}