[Baekjoon] 10973_이전 순열

Silver III

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

---

< 이전 순열 >

 

문제 풀이 

 

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

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

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

3을 확인했을 때 뒤에 4밖에 없으므로 3보다 큰 수 이므로 넘어간다.

5를 확인했을 때 3,4 같이 5보다 작은 값이 있으므로 다음 순열을 출력하기 위해 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 _10973_ { // 이전 순열

	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());

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

		ArrayList<Integer> list = new ArrayList<>();
		int idx = -1, num = -1;
		for (int i = n - 1; i >= 0; i--) {
			list.add(arr[i]);

			Collections.sort(list);
			if (arr[i] != list.get(0)) {
				for (int j = list.size() - 1; j >= 0; j--) {
					if (arr[i] > list.get(j)) {
						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 값을 제외한 값을 순서대로 출력한다.

---

---