[BAEKJOON] 백준 31870: 버블버블 (C#)

문제 링크

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

 

 

문제

민구는 원소의 개수가 N개이고 값이 서로 다른 정수 배열 A를 오름차순으로 만들고 싶다.

배열의 i번째 원소와 i+1번째 원소끼리 서로 위치를 바꿀 수 있고, 정렬 과정 중 언제든지 최대 딱 한 번 배열 전체의 순서를 뒤집을 수 있다.

원소를 교환하는 것, 배열 전체를 뒤집는 것 모두 1번의 횟수로 계산한다.

주어진 배열 A를 오름차순으로 만드는데 필요한 최소한의 횟수를 구하여라.

 

 

입력

첫 번째 줄에 배열 A의 원소 개수 N이 주어진다. (1≤N≤1000)

두 번째 줄에 A의 원소 정수 Ai가 공백을 사이에 두고 순서대로 주어진다. (1≤Ai≤10^6)

 

 

출력

첫 번째 줄에 주어진 배열 A를 오름차순으로 만드는데 필요한 최소한의 횟수를 출력한다.

 

 

 

통과한 답안

namespace _31870
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int sortCnt = SortCnt(arr);
            int reverseCnt = ReverseSortCnt(arr);

            Console.WriteLine(Math.Min(sortCnt, reverseCnt));
        }

        static int SortCnt(int[] arr)
        {
            int[] tmpArr = (int[])arr.Clone();
            int cnt = 0;
            int n = tmpArr.Length;

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = 0; j < n - i - 1; j++)
                {
                    if (tmpArr[j] > tmpArr[j + 1])
                    {
                        int tmp = tmpArr[j];
                        tmpArr[j] = tmpArr[j + 1];
                        tmpArr[j + 1] = tmp;

                        cnt++;
                    }
                }
            }

            return cnt;
        }

        static int ReverseSortCnt(int[] arr)
        {
            int[] tmpArr = (int[])arr.Clone();
            int cnt = 0;
            int n = tmpArr.Length;

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = 0; j < n - i - 1; j++)
                {
                    if (tmpArr[j] < tmpArr[j + 1])
                    {
                        int tmp = tmpArr[j];
                        tmpArr[j] = tmpArr[j + 1];
                        tmpArr[j + 1] = tmp;

                        cnt++;
                    }
                }
            }

            return cnt + 1;
        }
    }
}

 

주어진 정수 배열을 오름차순으로 정렬하려는데 사용할 수 있는 방법은 2가지가 있다.

i와 i+1번째의 원소의 위치를 바꾸는 것과 배열 전체의 순서를 뒤집는 것을 사용할 수 있는데

배열 전체의 순서를 뒤집는 것은 최대 한 번 사용할 수 있다.

이러한 조건이 있을 때, 배열을 오름차순으로 정렬하는 최소 횟수를 구하는 문제이다.

 

이 문제의 조건을 간략하게 생각해보면,

배열을 오름차순으로 정렬한 것과 내림차순으로 정렬한 것 + 1 중에

더 적은 값을 출력하는 문제이다.

 

따라서 주어진 배열을 오름차순으로 정렬하는 것과 내림차순으로 정렬하는 것

2가지의 메서드를 만들어서 횟수를 계산한 후에 더 작은 값을 출력하도록 하였다.

 

각각의 정렬은 문제의 제목에 맞게 버블 정렬을 이용하여 구현하였다.