[Baekjoon] 10972_다음 순열

Silver III

문제(출처: https://www.acmicpc.net/problem/10972)

---

< 다음 순열 >

 

문제 풀이 

 

만약 1 2 3 5 4가 주어졌다고 생각해 보자.

뒤에서부터 값을 탐색하면서 현재 값에서 뒤에 값을 탐색한다. 

4는 마지막 값이므로 넘어간다.

5를 확인했을 때 뒤에 4밖에 없으므로 5보다 작은 수 이므로 넘어간다.

3을 확인했을 때 5,4와 같이 3보다 큰 값이 있으므로 다음 순열을 출력하기 위해 4로 교체한다. 그 후에 남은 값을 오름차순으로 정렬한 후 출력한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class _10972_ { // 다음 순열

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		int arr[] = new int[n];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		ArrayList<Integer> list = new ArrayList<>();
		int num = -1;
		int idx = -1;

		for (int i = n - 1; i >= 0; i--) {
			list.add(arr[i]);

			Collections.sort(list, Collections.reverseOrder());

			if (list.get(0) != arr[i]) {
				for (int j = list.size() - 1; j >= 0; j--) {
					if (list.get(j) > arr[i]) {
						num = list.get(j);
						break;
					}
				}
				idx = i;
				break;
			}
		}

		if (num == -1) {
			System.out.println(-1);
		} else {
			boolean flag = false;
			for (int i = 0; i < idx; i++) {
				bw.write(arr[i] + " ");
			}
			bw.write(num + " ");
			for (int i = list.size() - 1; i >= 0; i--) {
				if (!flag && list.get(i) == num) {
					flag = true;
					continue;
				}
				bw.write(list.get(i) + " ");
			}
			bw.flush();
		}
	}
}

변수)
n : 순열 수
arr : 순열 값
list : 현재 값보다 큰 수를 찾기 위한 리스트
num, idx : 현재 값보다 큰 값, 교체할 인덱스

 

순열 개수 n을 입력받는다. 배열에 순열 값을 저장한다. 뒤에서부터 값을 확인하면서  다음 과정을 수행한다.

 

1) list에 값을 추가한다.

2) list를 내림차순으로 정렬한 후 0번째 값과 현재 값이 일치하는지 확인한다.

3) 일치한다면 현재 값보다 큰 값이 없으므로 계속해서 반복한다. 일치하지 않는다면 현재 값보다 큰 값이 있다는 뜻이므로 list에 있는 값을 탐색하여 현재 값보다 큰 값 중에서 가장 작은 값을 찾아 num에 저장한다. idx를 현재 위치로 저장한 후 종료한다.

 

만약 num이 -1이라면 다음 순열이 없다는 뜻이므로 -1을 출력한다. num 값이 있다면 arr의 0번째부터 idx전까지 값을 출력한다. 그 후에 num 값을 출력한다. list를 뒤에서부터 num 값을 제외한 값을 순서대로 출력한다.

---

---