CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/">BOJ</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/login?next=%2Fsubmit%2F10972">10972.다음순열</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : 중상</p></li><li><p>풀이시간 : 3h over</p></li><li><p>유형 : 수학, 조합론</p></li></ul><h2>문제</h2><p>1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.</p><p>사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.</p><p>N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.</p><ul><li><p>1, 2, 3</p></li><li><p>1, 3, 2</p></li><li><p>2, 1, 3</p></li><li><p>2, 3, 1</p></li><li><p>3, 1, 2</p></li><li><p>3, 2, 1</p></li></ul><h2>입력</h2><p>첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.</p><h2>출력</h2><p>첫째&nbsp;줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.</p><h2>예제 입력 1 복사</h2><pre spellcheck="false"><code>4
1 2 3 4</code></pre><h2>예제 출력 1 복사</h2><pre spellcheck="false"><code>1 2 4 3</code></pre><h2>예제 입력 2 복사</h2><pre spellcheck="false"><code>5
5 4 3 2 1</code></pre><h2>예제 출력 2 복사</h2><pre spellcheck="false"><code>-1</code></pre><h3>문제 풀이 접근</h3><p>이 문제를 접근하기 전에, 사실 10973.이전 순열 문제를 먼저 접근했다. <br>그 문제를 잘못 읽어 고정된 마지막 순열의 이전 순열로 보고 잘못풀어 시간적 낭비를 하였고, 원리를 이해하기 위해 구글링을 하던 중, 이전 순열을 먼저 설명하는 내용을 확인하여 바꿔서 이전 순열을 먼저 풀었다.</p><p>이 문제는 먼저 규칙성을 찾는 것이 우선이다.</p><p>4개의 수 1 2 3 4 가 주어졌다고 하면, 아래와 같은 수열이 생긴다.<br><br>1 2 3 4<br>1 2 4 3<br>1 2 4 3<br>1 3 2 4<br>1 3 4 2<br>1 4 2 3<br>1 4 3 2<br>2 1 3 4<br>2 1 4 3<br>2 3 1 4&nbsp;<br>2 3 4 1<br>2 4 1 3<br>2 4 3 1<br>3 1 2 4<br>3 1 4 2<br>3 2 1 4<br>3 2 4 1<br>3 4 1 2<br>3 4 2 1<br>4 1 2 3<br>4 1 3 2<br>4 2 1 3<br>4 2 3 1<br>4 3 1 2<br>4 3 2 1</p><p>만약 1 2 3 4가 주어졌다고 가정을 하면, <br><br>1.오른쪽 부터 배열을 체크하여 내림 차순이 시작되는 부분((n-1) &lt; (n))을&nbsp;체크한다.<br>2.&nbsp; n-1 을 기준으로 왼쪽 영역, 오른쪽 영역을 구분한다.<br>3. 오른쪽 영역의 오른쪽 원소부터 왼쪽 영역의 오른쪽 원소에서 왼쪽으로 [왼쪽 영역의 원소]&nbsp;&lt;&nbsp;[오른쪽 영역의 오른쪽 원소] 을 찾는다.<br>4. 발견한다면 둘을 스왑해주고, 오른쪽 영역을 오름차순 정렬하여 출력한다.</p><p>ex ) 2 3 4 1 이라면,<br>2 [3] [4] 1 이 부분에서 내림차순을 찾았고,&nbsp;<br>2 3 / 4 1 로 오른쪽 왼쪽 영역을 분리한다.<br>4 1 의 1 부터 2 3 배열의 3 =&gt; 2 순서로 비교한다.<br>1은 왼쪽 영역보다 큰 경우가 없으니 패스, 4는 왼쪽 영역의 가장 오른쪽 원소 3보다 크기 때문에, 스왑한다.<br>2 4 / 3 1 이 된 후 오른쪽 영역을 오름차순 정렬한다.</p><h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

/*
 * URL : https://www.acmicpc.net/submit/10972
 */

namespace CodingTestProj
{
    internal class Program
    {
        public static string input;
        public static int _standardIndex; // (n) &lt; (n-1) 가 되는 기준

        static void Main(string[] args)
        {
            _standardIndex = -1;
            int cnt = Int32.Parse(Console.ReadLine());
            input = Console.ReadLine().Trim().Replace(" ", "");

            for (int i = input.Length - 1; i &gt; 0; --i)
            {
                int n = Int32.Parse(input[i].ToString());
                int prevn = Int32.Parse(input[i - 1].ToString());

                if (n &gt; prevn)
                {
                    _standardIndex = i - 1;
                    break;
                }
            }
            // 분리되는 기준점 찾기

            if (_standardIndex == -1)
            {
                Console.Write("-1");
                return;
            }
            // 못 찾았다면, -1 출력 및 종료

            string leftStr = input.Substring(0, _standardIndex + 1);
            string rightStr = input.Substring(_standardIndex + 1);

            // 찾았다면 왼쪽 오른쪽 영역 분리

            bool _isChange = false;

            for (int i = rightStr.Length - 1; i &gt;= 0; --i)
            {
                for (int j = leftStr.Length - 1; j &gt;= 0; --j)
                {
                    if (Convert.ToInt32(rightStr[i]) &gt; Convert.ToInt32(leftStr[j]))
                    {
                        char[] rightArr = rightStr.ToCharArray();
                        char[] leftArr = leftStr.ToCharArray();

                        char temp = rightArr[i];
                        rightArr[i] = leftArr[j];
                        leftArr[j] = temp;

                        rightStr = new string(rightArr);
                        leftStr = new string(leftArr);
                        _isChange = true;
                        break;
                    }
                }

                if (_isChange == true)
                    break;
            }
            // 오른쪽 영역의 오른쪽 원소부터 왼쪽 영역의 오른쪽 원소부터 차례로 큰 부분을 찾는 로직

            char[] rightArr2 = rightStr.ToCharArray();
            Array.Sort(rightArr2);
            rightStr = new string(rightArr2);
            // 오른쪽 영역을 오름차순 정렬

            for (int i = 0; i &lt; leftStr.Length; ++i)
            {
                Console.Write($"{Int32.Parse(leftStr[i].ToString())}");
                Console.Write($" ");
            }

            for (int i = 0; i &lt; rightStr.Length; ++i)
            {
                Console.Write($"{Int32.Parse(rightStr[i].ToString())}");

                if (i != rightStr.Length - 1)
                    Console.Write($" ");
            }

            // 왼쪽 먼저 출력하고, 오른쪽 영역 차례로 출력.
        }
    }
}</code></pre><h3><strong>코드 결과 - 아직 풀지 못함.</strong></h3><p></p><p></p><p></p><p></p><p></p><p></p><p></p><p></p><p></p><p></p><p></p><p></p>

혼자서 다시푸는 코딩테스트 준비 일지 - 21