다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 10972.다음순열
사용언어 : C#
난이도 : 중상
풀이시간 : 3h over
유형 : 수학, 조합론
문제
1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
입력
첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.
출력
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
예제 입력 1 복사
4
1 2 3 4예제 출력 1 복사
1 2 4 3예제 입력 2 복사
5
5 4 3 2 1예제 출력 2 복사
-1문제 풀이 접근
이 문제를 접근하기 전에, 사실 10973.이전 순열 문제를 먼저 접근했다.
그 문제를 잘못 읽어 고정된 마지막 순열의 이전 순열로 보고 잘못풀어 시간적 낭비를 하였고, 원리를 이해하기 위해 구글링을 하던 중, 이전 순열을 먼저 설명하는 내용을 확인하여 바꿔서 이전 순열을 먼저 풀었다.
이 문제는 먼저 규칙성을 찾는 것이 우선이다.
4개의 수 1 2 3 4 가 주어졌다고 하면, 아래와 같은 수열이 생긴다.
1 2 3 4
1 2 4 3
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
만약 1 2 3 4가 주어졌다고 가정을 하면,
1.오른쪽 부터 배열을 체크하여 내림 차순이 시작되는 부분((n-1) < (n))을 체크한다.
2. n-1 을 기준으로 왼쪽 영역, 오른쪽 영역을 구분한다.
3. 오른쪽 영역의 오른쪽 원소부터 왼쪽 영역의 오른쪽 원소에서 왼쪽으로 [왼쪽 영역의 원소] < [오른쪽 영역의 오른쪽 원소] 을 찾는다.
4. 발견한다면 둘을 스왑해주고, 오른쪽 영역을 오름차순 정렬하여 출력한다.
ex ) 2 3 4 1 이라면,
2 [3] [4] 1 이 부분에서 내림차순을 찾았고,
2 3 / 4 1 로 오른쪽 왼쪽 영역을 분리한다.
4 1 의 1 부터 2 3 배열의 3 => 2 순서로 비교한다.
1은 왼쪽 영역보다 큰 경우가 없으니 패스, 4는 왼쪽 영역의 가장 오른쪽 원소 3보다 크기 때문에, 스왑한다.
2 4 / 3 1 이 된 후 오른쪽 영역을 오름차순 정렬한다.
정답 작성 코드 (C#)
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) < (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 > 0; --i)
{
int n = Int32.Parse(input[i].ToString());
int prevn = Int32.Parse(input[i - 1].ToString());
if (n > 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 >= 0; --i)
{
for (int j = leftStr.Length - 1; j >= 0; --j)
{
if (Convert.ToInt32(rightStr[i]) > 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 < leftStr.Length; ++i)
{
Console.Write($"{Int32.Parse(leftStr[i].ToString())}");
Console.Write($" ");
}
for (int i = 0; i < rightStr.Length; ++i)
{
Console.Write($"{Int32.Parse(rightStr[i].ToString())}");
if (i != rightStr.Length - 1)
Console.Write($" ");
}
// 왼쪽 먼저 출력하고, 오른쪽 영역 차례로 출력.
}
}
}