[Hacker Rank, 해커랭크] New Year Chaos 문제 및 풀이 ( C# )

문제 링크: https://www.hackerrank.com/challenges/new-year-chaos/problem

New Year Chaos | HackerRank

문제 요약

난이도: Medium

 

- 새해 첫날 원더랜드 롤러코스터를 타기 위해 줄을 서 있습니다.

- 줄에 서있는 사람들에게 먼저 온 순서대로 번호 스티커를 배부했습니다. ( 5명이면 1,2,3,4,5 이렇게 )

- 뒷 번호에 있는 사람들은 최대 2번 뇌물을 주어 앞번호를 가진 사람과 위치를 바꿀 수 있습니다.

- input으로 주어진 뒤죽박죽 된 번호들을 보고 몇 번의 위치가 바뀌었는지 횟수를 output으로 보여주면 됩니다.

- 만약, 한 사람이 3번 이상 뇌물을 주었다면 "Too chaotic"을 출력하면 됩니다.

---

 

문제 풀이

이 문제를 보면서 크게 2가지의 해결 방법이 생각났습니다.

1. 시뮬레이션을 반대로 직접 돌려보기

2. 직접 돌려보지 않고 결과를 보고 계산하기

 

처음엔 2번의 방법으로 풀려고 노력했는데 생각보다 잘 되지 않아 1번의 방법으로 우회했습니다.

 

---

직접 시뮬레이션 돌려보기

 

이미 다 섞여버린 대기열을 보고 누가 몇 번씩 Swap했는지 알아내려면 처음 정렬 됐을 때로 돌아가야 합니다.

그래서 섞을때 들어간 룰 중 뒷번호를 가지고 뒤에 있는 사람만이 앞번호에게 뇌물을 줄 수 있는데 

반대로 "뒷번호가 앞번호 앞에 있을 때 Swap 한다"라는 룰을 가지고 시뮬레이션을 하였습니다.

 

예시를 들어보겠습니다.

 

2

1

5

3

4

만약 이렇게 섞인 배열이 있다면 다시 1,2,3,4,5로 돌아가는 시뮬레이션을 진행해야 합니다.

 

1

2

5

3

4

2(뒷번호) 뒤에 1(앞번호)가 있으므로 둘이 Swap을 해줍니다.

 

2

1

3

5

4

5(뒷번호) 뒤에 3(앞번호)가 있으므로 Swap!

 

2

1

3

4

5

5(뒷번호) 뒤에 4(앞번호)가 있으므로 Swap!

 

다시 앞으로 돌아가서!

1

2

3

4

5

2(뒷번호) 뒤에 1(앞번호)가 있으므로 Swap!

 

---

이렇게 하면 원래대로 숫자들이 돌아왔습니다!

따라서 이것을 반대로 진행하면 몇 번 Swap이 일어났는지 알아낼 수 있겠죠.

 

하지만 한가지 빠뜨린 게 있습니다..!

바로 input으로 준 대기열의 모든 사람들이 최대 2번까지만 뇌물을 주었는지 체크해야 합니다.

대기열과 똑같은 길이의 int 배열을 만들어 각자 몇 번을 Swap 했는지 확인할 수 있습니다.

만약 SwapCount를 올릴때 2를 초과하는 경우 바로 Too chaotic을 출력하고 종료하면 됩니다.

 

이 부분은 코드로 대체하겠습니다~!

 

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution
{

    // Complete the minimumBribes function below.
    static void minimumBribes(int[] q)
    {
        var swapCount = 0;                  // Swap 횟수 변후
        var countLen = new int[q.Length];   // 각 사람들의 Swap 횟수
        var isSwaped = false;               // 스왑을 하였는지 체크용 번수

        while (true)
        {
            isSwaped = false;
            for (var i = 0; i < q.Length; ++i)
            {
                if (i == 0)
                    continue;

                // 현재 위치의 번호랑 이전 위치의 번호랑
                // 비교하여 이전 위치의 번호가 더 높을 경우 Swap
                var curNum = q[i];
                var prevNum = q[i - 1];

                if (prevNum > curNum)
                {
                    // Swap
                    isSwaped = true;

                    q[i - 1] = curNum;
                    q[i] = prevNum;

                    ++swapCount;
                    if (++countLen[prevNum - 1] > 2)
                    {
                        Console.WriteLine("Too chaotic");
                        return;
                    }
                }
            }

            if (isSwaped == false)
                break;
        }

        Console.WriteLine(swapCount);
    }

    static void Main(string[] args)
    {
        int t = Convert.ToInt32(Console.ReadLine());

        for (int tItr = 0; tItr < t; tItr++)
        {
            int n = Convert.ToInt32(Console.ReadLine());

            int[] q = Array.ConvertAll(Console.ReadLine().Split(' '),
                qTemp => Convert.ToInt32(qTemp));
            minimumBribes(q);
        }
    }
}

 

감사합니다 :)