[백준] 1083 - 소트

1. 문제

1083번: 소트

2. 개요

동일한 수가 없는 크기 N의 배열이 있다.

이 배열을 소트하려고 하는데, 한 번 소트할 때 연속된 두 개의 원소만 교환이 가능하다.

교환 제한 횟수 S가 주어졌을 때, 이 배열을 소트하여 얻을 수 있는 사전순으로 가장 끝에 오는 배열을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

가장 앞의 인덱스부터 탐색한다. 해당 인덱스 + 남은 교환 횟수번째 인덱스까지 탐색하여 가장 큰 수를 찾는다. 이 가장 큰 수를 맨 앞에 위치시키고 그 앞에 있던 수들을 한 칸씩 뒤로 밀어주면 된다.

이 작업을 남은 교환 횟수가 0이 되거나 모든 인덱스에 대해 탐색이 종료될 때까지 반복한 후 갱신된 배열을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

nums = list(map(int, sys.stdin.readline().split()))

S = int(sys.stdin.readline())

leftcount = S

for i in range(N):
    maxValue = 0
    maxidx = i

    for j in range(i, i + leftcount + 1):
        if j >= N:
            break

        if nums[j] > maxValue:
            maxValue = nums[j]
            maxidx = j
        
    for j in range(maxidx, i, -1):
        nums[j] = nums[j - 1]

    nums[i] = maxValue
    leftcount -= maxidx - i

    if leftcount == 0:
        break

print(*nums)

3-3. C#

using System.Globalization;

namespace boj_1083
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int S = int.Parse(Console.ReadLine());

            int leftCount = S;

            for (int i = 0; i < N; i++)
            {
                int maxValue = 0;
                int maxidx = i;

                for (int j = i; j < i + leftCount + 1; j++)
                {
                    if (j >= N)
                        break;

                    if (nums[j] > maxValue)
                    {
                        maxValue = nums[j];
                        maxidx = j;
                    }
                }

                for (int j = maxidx; j > i; j--)
                {
                    nums[j] = nums[j - 1];
                }

                nums[i] = maxValue;
                leftCount -= maxidx - i;

                if (leftCount == 0)
                    break;
            }

            foreach (int num in nums)
            {
                Console.Write($"{num} ");
            }
        }
    }
}