백준#1377 - 버블 소트

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

1377번: 버블 소트

정렬로 분류된 1377 버블 소트 문제 입니다.

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;
 
namespace _1377
{
    class Program
    {
        public class Pair : IComparable
        {
            public int index;
            public int value;
 
            public Pair(int index, int value)
            {
                this.index = index;
                this.value = value;
            }
            public int CompareTo(Object obj)
            {
                Pair other = obj as Pair;
                if (other.value == this.value)
                    return this.index.CompareTo(other.index);
 
                return this.value.CompareTo(other.value);
            }
        }
        static void Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine());
            var numList = new List<Pair>();
            for (int i = 0; i < count; i++)
                numList.Add(new Pair(i, int.Parse(Console.ReadLine())));
 
            numList.Sort();
 
            int maxMoveCount = 0;
 
            for(int i = 0; i < numList.Count; i++)
            {
                if (maxMoveCount < numList[i].index - i)
                    maxMoveCount = numList[i].index - i;
            }
 
            Console.WriteLine(maxMoveCount + 1);
        }
    }
}
 

문제에 나온 코드를 간략히 정리하겠습니다.

버블 소트는 맨앞(인덱스가 0인)수 부터 바로 뒤의 수를 확인하며 뒤의 수보다

크다면 다음것과 swap하는 방식입니다. 문제에 나온 한번의 수행으로

배열의 가장 큰 수 하나가 맨 뒤로 가는 결과가 나옵니다.

 

10, 5, 1, 2, 3 이 예시에서 한번의 과정을 거치면

10이 맨 뒤로 가게 됩니다.

 

하지만 단순히 가장 큰 수만 뒤로 보내는 것이 아닙니다.

2, 1, 3, 2 이런 경우에

한번의 수행으로 가장 처음 2가 한칸 뒤로 가고 3이 가장 뒤로 갑니다.

1, 2, 2, 2, 3이 나오며 한번에 정렬이 완료됩니다.

 

즉 3을 만나기 전까지 앞의 수에서 가장 큰 수가 3을 만나는 지점까지 오고,

3을 가장 뒤로 보내는 작업을 할 것입니다.

 

 

이 문제는 각 숫자가 앞으로 얼마나 움직였느냐! 가 핵심이 되겠습니다.

 

ex)      3 2 1 3 2 1

index   0 1 2 3 4 5

이렇게 있다고 생각하겠습니다.

이걸 정렬 하면

 

1 1 2 2 3 3

이렇게 될것입니다.

첫번째 1은 3번째 1이 맨 앞으로 온 것입니다. 앞으로 두칸 이동한 것이죠.

이 뜻은 앞에 어떤 수든 간에 두 수가 1의 뒤로 이동했다는 뜻입니다.

최소 2번의 버블소트 과정을 거쳤다는 것이죠.

 

두번째 1은 마지막 1이 두번째로 온 것입니다. 앞으로 4칸 이동 했습니다.

4번의 버블소트 과정을 거쳐 현재의 자리에 온 것입니다.

 

이걸 구하기 위해 정렬 전의 인덱스와 정렬 후의 새로 받은 인덱스를 비교해야 합니다.

           값                  인덱스

정렬전 : 3 2 1 3 2 1 => 0 1 2 3 4 5

정렬후 : 1 1 2 2 3 3 => 2 5 1 4 0 3

 

정렬이 되며 인덱스가 전부 섞였고 정렬후의 인덱스에서 정렬전 인덱스를 빼주면

해당 값이 앞으로 얼마나 이동했는지 알 수 있습니다.

 

그 중 가장 큰 것을 골라주면 되겠습니다.

 

위의 경우에서는 정렬전 5번 인덱스의 1이 4번의 이동으로 가장 많이 이동했습니다.

답은 4 + 1(정렬이 완료된 후 한번의 확인 필요) 되겠습니다.

 

주의할 점은 정렬전의 값과 인덱스를 묶어 정렬해야 합니다

이 경우 값이 같다면 반드시 인덱스에 대해 정렬해 주세요.

문제 코드의 경우 값이 클 때만 swap을 하므로 위의 예시에서

정렬전 마지막 1이 정렬전 3번째 1 앞으로 올 수 없습니다.

이를 고려해야 합니다.