[백준 10972, 10973] 다음순열, 이전순열 (Java)

문제

10972 다음순열 https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

설계

 

설계1: dfs 완전탐색

순열을 구하는 문제이니 dfs 완전탐색으로 접근하면 되지 않을까? 하지만, dfs 완전탐색은 모든 경우의 수에 대해 탐색하는 것이므로 Worst Case에 대해 고려해야 한다.

• Worst Case: N=10,000  즉, 10000! 경우의 수에 대해 탐색해야하므로 "시간초과"

 

설계2: 순열의 특성을 고려한 구현으로 접근

주어진 정보는 순열이다. 따라서, 주어진 순열을 적절히 조작하면 다음 순열을 만들 수 있지 않을까 생각했고, 순열의 규칙에 대해 파악먼저 하려고 했다.

 

위의 사진에서 [1 2 5 4 3] 의 다음 순열에 대해 생각해보자.

[1 2 5 4 3]는 [1 2] [오름차순(역방향기준)]으로 정의할 수 있다. 이 의미는 [1 2]로 시작하는 순열의 마지막 수이다.

 

1. 마지막 수이기 때문에 [1 2]로 시작하는 순열은 더 이상 없다.
2. 다음순열은 [1 2]의 마지막 수인 2와 오름차순 중에서 바로 다음 큰 수인 3를 교체한 [1 3]로 시작하는 순열이 된다. *기존의 오름차순은 여전히 오름차순이다. (∵ 2의 바로 다음 큰수인 3과 교체했기 때문) => [1 3] [5 4 2]
3. [1 3]으로 시작하는 순열의 첫번째 수이기 때문에 기존의 오름차순 -> 내림차순으로 만들어야 한다. => [1 3] [2 4 5]

 

 

 

 

구현

 

1. 오름차순 판별

목표: 교체인덱스(replaceIdx) 찾기 -> 오름차순 끝나는 idx-1 인덱스

int replaceIdx = -1; //교체인덱스
		//오름차순이 끝나는 인덱스-1 인덱스 찾기
		for (int i=num.length-1; i>0; i--) {
			if(num[i-1] < num[i]) {
				replaceIdx = i-1;
				break;
			}
		}

 

 

• Edge Case: replace의 초기값을 -1로 둔 이유는 Edge Case 판별을 위해서이다. 이 문제의 Edge Case는 "다음 순열"이 없는 경우일 것이다. [5 4 3 2 1]을 생각해보자. 위의 로직 상, num[i-1] < num[i]인 값은 존재하지 않고, replaceIdx의 값은 여전히 -1이다. 다음 로직을 처리하기 전, replaceIdx == -1 (Edge case)에 대한 처리를 수행해주면 된다.

 

2. replaceIdx의 값보다 바로 다은 큰 값과 swap

//오름차순 중 교체인덱스의 값보다 바로다음 큰 값의 인덱스 찾기
		if (replaceIdx == -1) {
			System.out.println(-1);
		}
		else {
			int replaceIdx2 = -1;
			for (int i=num.length-1; i>0; i--) {
				if(num[replaceIdx] < num[i]) {
					replaceIdx2 = i;
					break;
				}
			}
		
			//스왑
			swap(num, replaceIdx, replaceIdx2);
            
			...
         }
 }

 

 

3. 기존의 오름차순 -> 내림차순

...
decending(num, replaceIdx+1);

...
	private static void decending(int[] num, int decendStartIdx) {

		int decendLastIdx = num.length-1;
		
		while (decendStartIdx < decendLastIdx) {

			swap(num, decendStartIdx++, decendLastIdx--);	
			
		}
		
	}

 

 

 

 

 

전체 코드

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		int replaceIdx = -1; //교체인덱스
		//(역기준)오름차순이 끝나는 인덱스의 -1인덱스 값과 오름차순 중 그 인덱스값보다 바로다음 큰 값 교체
		//오름차순이 끝나는 인덱스-1 인덱스 찾기
		for (int i=num.length-1; i>0; i--) {
			if(num[i-1] < num[i]) {
				replaceIdx = i-1;
				break;
			}
		}
		//오름차순 중 교체인덱스의 값보다 바로다음 큰 값의 인덱스 찾기
		if (replaceIdx == -1) {
			System.out.println(-1);
		}
		else {
			int replaceIdx2 = -1;
			for (int i=num.length-1; i>0; i--) {
				if(num[replaceIdx] < num[i]) {
					replaceIdx2 = i;
					break;
				}
			}
		
			//스왑
			swap(num, replaceIdx, replaceIdx2);

			//교체인덱스+1 인덱스부터 끝까지 내림차순 정렬
			decending(num, replaceIdx+1);
			
			printArr(num);	
		}
		
	}

	private static void printArr(int[] num) {
		for (int i=0; i<num.length; i++) {
			System.out.print(num[i] + " ");
		}
		
	}

	private static void decending(int[] num, int decendStartIdx) {
		int decendLastIdx = num.length-1;
		
		while (decendStartIdx < decendLastIdx) {
			swap(num, decendStartIdx++, decendLastIdx--);	
		}
		
	}

	private static void swap(int[] num, int replaceIdx, int replaceIdx2) {
		int tmp = num[replaceIdx];
		num[replaceIdx] = num[replaceIdx2];
		num[replaceIdx2] = tmp;
	}
}

 

 

결과

 

 

 

요약

1. dfs, bfs 등의 접근으로 완전탐색 할 시, Worst Case 판별하여 접근가능 여부 판단

2. 순열의 특성 파악할 수 있는 문제