(2024-10-28) 1 문제 : 백준 - 1377 (버블 소트)

 

버블소트를 그대로 구현하면 N^2 의 시간복잡도로 인해, 시간 초과가 발생하므로 버블소트를 사용하지 않고 다른 방법을 통해 버블 소트 실행 시에 외부 반복문이 몇 회 발생하는지 예측하는 문제이다.

 

아이디어를 떠울리는게 꽤나 오래 걸렸다. 처음엔 RIS (가장 긴 증가하는 부분 수열)을 구해보았고, 그 다음은 중복된 값을 고려하기 정렬된 배열과 비교하며 정렬되어 있지 않은 숫자들의 수를 구해보았다.

 

하지만, 이 방식이 틀렸던 이유는 한 반복문에서 2개의 숫자만 자리를 찾아가는 것이 아니기 때문이었다.

(2 1 3 4 6 5) 에선 한 번의 반복문으로 (2 1 3 4 5 6)으로 정렬이 되지만, 위에서 언급한 방식으로 계산하면 2회의 반복문이 돌았다는 값이 나와버린다. 

 

그러므로 다른 아이디어를 생각해봤는데, 버블 정렬은 현재 선택한 인덱스의 숫자가 뒤 쪽의 인덱스로 제 자리를 찾아갈 때엔 몇 번의 반복문이 발생하는지 예측할 수 없지만 반대로 뒤에 있던 숫자가 앞으로 이동하는 경우엔 몇 번의 반복문이 발생하는지 예측할 수 있다. 왜냐하면, 버블정렬은 앞의 숫자를 뒤로 이동하는 것이 중점이기 때문에 뒤에 있는 숫자는 한 번의 반복문당 1칸씩만 앞으로 이동하기 때문이다. (만약 버블정렬을 반대로 구현하여 뒤에서부터 앞으로 이동하게 했다면 반대로 구현해야 할 것이지만, 문제에서 제공된 버블정렬은 그렇지 않으니..)

 

즉, 모든 인덱스에 대해 (정렬 전에 위치하던 인덱스 - 정렬된 상태에서 위치하는 인덱스)의 최대값이 반복문이 수행된 횟수가 되는 것이다. 

 

하지만, 한 가지 고려해야 할 것은 정렬 과정에서 stable하게 정렬해야 한다는 것이다.

{값, 기존 인덱스} 를 배열에 담아 정렬할 때 정렬 전에 1이라는 값이 3번 인덱스와 4번 인덱스에 위치했다면, 정렬 후에도 {1,4}는 {1, 3} 뒤에 있어야 한다. 그래야지 숫자의 이동 거리를 제대로 예측할 수 있다.

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

bool Compare(const std::pair<int, int>& _Left, const std::pair<int, int>& _Right)
{
    if (_Left.first == _Right.first)
    {
        return _Left.second < _Right.second;
    }

    return _Left.first < _Right.first;
}

int main()
{
    Init(); 
    
    int NumSize = 0;
    std::cin >> NumSize;

    std::vector<std::pair<int, int>> Nums(NumSize);

    for (int i = 0; i < Nums.size(); i++)
    {
        std::cin >> Nums[i].first;
        Nums[i].second = i;
    }

    std::sort(Nums.begin(), Nums.end(), Compare);
    
    int Answer = -1;

    for (int i = 0; i < NumSize; i++)
    {
        Answer = std::max(Answer, Nums[i].second - i);
    }

    std::cout << Answer + 1;

    return 0;
}