[백준 - Java] 10972번 : 다음 순열 / 10973 : 이전 순열

문제

www.acmicpc.net/problem/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을 출력한다.

 

 

단순히 생각한 나의 사고 과정과 코딩 과정을 기록한다.

다시끔 보면서 반성해보자.

1. 첫 번째 생각

기존의 순열 만들기 코드를 이용해서 찬찬히 순열을 만들어 가다가!

입력으로 주어진 값과 같은 순열을 발견하면 그다음 순열 출력해야지!

(근데 입력이랑 같은 순열이 아니라 다음 순열을 출력하는거닌까 boolean flag = false 만들고

같은 순열 발견하면 true로 바꾸고

다음 순열 구하기 타임에서 true라면 순열 출력하라고 해야지)

 

거기다가 마지막 순열이면 -1 출력해야지!

(마지막 순열이라는 뜻은 예를 들어 N이 4인 순열일 경우, 총순열의 개수는 4! = 4*3*2*1 = 24

count 변수 놔두고 24랑 같아지면 -1 출력하라고 하면 되겠다)

실패 - 시간초과

실패 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[] input;
	static boolean flag = false;
	static int factorial = 1;
	static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		input = new int[N]; //주어진 순열 담을 배열
		int[] arr = new int[N]; //시작 순열
		for(int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
			arr[i] = i + 1;
			factorial *= (i+1);
		}
		
		boolean[] v = new boolean[N];
		int[] output = new int[N];
		
		per(arr, v, N, 0, output);
		
	}

	public static void per(int[] arr, boolean[] v, int n, int r, int[] output) {
		if(r == n) {
			count++;
			
			if(flag) {
				for(int i = 0; i < output.length; i++) {
					System.out.print(output[i] + " ");
				}
				System.exit(0);
			}
			
			if(Arrays.equals(input, output)) {
				if(count == factorial) {
					System.out.println(-1);
				} else {
					flag = true;
				}
			}
			
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(!v[i]) {
				v[i] = true;
				output[r] = arr[i];
				per(arr, v, n, r+1, output);
				v[i] = false;
			}
		}
	}
}

 

2. 시간을 줄이기 위한 코드 수정

- BufferedReader, BufferWriter, StringBuilder 사용하기

- 같은 순열 찾고 나면 그냥 바로 System.exit(0)으로 재귀 종료해서 시간 단축해보기

실패 - 시간 초과

이 방법이 아니다... 고민을 하다가

다른 사람들의 코드와 해설 참고ㅠ_ㅠ

3. 참고 포스트

dundung.tistory.com/58

백준 10972 이전 순열 & 10973 다음 순열 Java

이 분의 포스트를 보면 이해가 잘 된다!

이런 식으로 구해야 O(N)의 시간 복잡도로 시간 초과 나지 않게 구현이 가능하다 이 말이다...

성공 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		if(nextPermutaion(arr)) {
			for(int i : arr)
				sb.append(i + " ");
		} else {
			sb.append(-1);
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
	
	public static boolean nextPermutaion(int[] arr) {
		int i = arr.length-1;
		while(i > 0 && arr[i] < arr[i-1]) {
			i--;
		}

		if(i == 0) //마지막 순열인 경우
			return false;
		
		int j = arr.length-1;
		while(arr[i-1] > arr[j]) {
			j--;
		}
		swap(arr, i-1, j);
		
		j = arr.length-1;
		while(i < j) {
			swap(arr, i, j);
			i++;
			j--;
		}
		
		return true;
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

10973번 : 이전 순열

다음 순열과 같은 문제이다.

다음 대신 이전을 찾는 것!

기존의 다음 순열 코드에서 부등호만 바꿔준다면 쉽게 구할 수 있다! 원리는 같으닌까

성공코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int[] arr = new int[N];
		for(int i = 0; i < N; i++)
			arr[i] = sc.nextInt();
	
		
		if(prePermutaion(arr)) {
			for(int i : arr)
				System.out.print(i + " ");
		} else {
			System.out.println(-1);
		}
	}
	
	public static boolean prePermutaion(int[] arr) {
		int i = arr.length-1;
		
		while(i > 0 && arr[i] > arr[i-1]) { //부등호 수정
			i--;
		}

		if(i == 0) //첫 번째 순열인 경우
			return false;
		
		int j = arr.length-1;
		while(arr[i-1] < arr[j]) { //부등호 수정
			j--;
		}
		swap(arr, i-1, j);
		
		j = arr.length-1;
		while(i < j) {
			swap(arr, i, j);
			i++;
			j--;
		}
		
		return true;
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2310972/src/Main.java

KwonMinha/BOJ