[백준 10972번] 자바/다음 순열

문제

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을 출력한다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ10972 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());
		int nums[] = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		// 반복문 끝난 이후에도 i값 확인하기 위해 밖으로 뺌
		int i;	
		for (i = nums.length - 1; i > 0; i--) {
			// 배열의 뒤쪽 값(인덱스 i)이 앞쪽 값(인덱스 i-1)보다 더 크다면, 
            // 즉 내림차순 정렬이 안되어있다면 if문 들어옴
			if(nums[i] > nums[i - 1]) {
				// 내림차순 정렬이 안되어있는 배열 범위에서 (i-1 제외) 
                // 가장 작은 값을 젤 앞(i-1 자리)으로 빼줌
				swap(nums, i - 1, getMinIndex(nums, i));
				
				// 나머지 부분 오름차순 정렬
				Arrays.sort(nums, i, nums.length);
				break;
			}
		}
		
		if(i == 0) {
			System.out.println(-1);
		} else {
			for (int num : nums) {
				System.out.print(num + " ");
			}
		}
		
	}	
	
	// 배열 안의 두 값을 바꿔줌
	static void swap(int arr[], int index1, int index2) {
		int temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}
	
	// 배열 특정 범위내에서 가장 작은 값의 인덱스 반환
	static int getMinIndex(int arr[], int start) {
		int min = arr[start];
		int index = start;
		
		for (int i = start + 1; i < arr.length; i++) {
			if(arr[i] < min) {
				min = arr[i];
				index = i;
			}
		}
		
		return index;
	}
}

계속 틀렸다고 나와서 고민하고 있었는데,

어떤 테스트케이스가 문제인지 찾음

 

5
3 5 2 4 1

 

추후 코드 수정할 예정...

---

코드 수정하며 차근히 다시 그려보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ10972 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int n = Integer.parseInt(br.readLine());
		int nums[] = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		// 반복문 끝난 이후에도 i값 확인하기 위해 밖으로 뺌
		int i;	
		for (i = nums.length - 1; i > 0; i--) {
			// 배열의 뒤쪽 값(인덱스 i)이 앞쪽 값(인덱스 i-1)보다 더 크다면, 즉 내림차순 정렬이 안되어있다면 if문 들어옴
			if(nums[i] > nums[i - 1]) {
				// 내림차순 정렬이 안되어있는 배열 범위에서 (i-1 제외) 가장 작은 값을 젤 앞(i-1 자리)으로 빼줌
				swap(nums, i - 1, getIndex(nums, i));
				
				// 나머지 부분 오름차순 정렬
				Arrays.sort(nums, i, nums.length);
				break;
			}
		}
		
		if(i == 0) {
			System.out.println(-1);
		} else {
			for (int num : nums) {
				System.out.print(num + " ");
			}
		}
		
	}	
	
	// 배열 안의 두 값을 바꿔줌
	static void swap(int arr[], int index1, int index2) {
		int temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}
	
	// 배열 특정 범위내에서 start-1 위치의 값보다 큰 값 중 가장 작은 값 반환
	static int getIndex(int arr[], int start) {
		int min = Integer.MAX_VALUE;
		int index = 0;
		
//		System.out.printf("min값은 %d, arr[start]는 %d\n", min, arr[start]);
		
		for (int i = start; i < arr.length; i++) {
//			System.out.printf("현재 i값은 %d, arr[i]는 %d\n", i, arr[i]);
			
			if(arr[i] > arr[start - 1] && arr[i] < min) {
				min = arr[i];
				index = i;
//				System.out.printf("if문 들어옴! 현재 min값은 %d, index는 %d\n", min, index);
			}
		}
		
		return index;
	}
}

얘는 최종 코드!! 드뎌 맞았다!!

마지막에 코드 짤 때 안됐던 테스트 케이스는

4

2 4 3 1

이다.

틀렸다고 나오시는 분들 계시면 저 값으로 함 해보시길!