10972_다음 순열 & 10973_이전 순열 (JAVA)

10972_다음 순열

10972번: 다음 순열

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] num = new int[n];

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

		boolean flag = false;

		Loop:
		for(int i=n-1; i>=1; i--){
			if(num[i-1]<num[i]){
				flag = true;
				for(int j=n-1; j>=i; j--){
					if(num[i-1]<num[j]){
						int temp = num[i-1];
						num[i-1] = num[j];
						num[j] = temp;

						Arrays.sort(num, i, n);
						break Loop;
					}
				}
			}
		}

		if(!flag)
			sb.append(-1);
		else{
			for(int i=0; i<n; i++){
				sb.append(num[i]).append(" ");
			}
		}

		System.out.print(sb);
		br.close();
	}
}

 

예) 6 2 4 5 3 1 일때

    ① 오른쪽부터 num[i-1]<num[i] 인 수 찾기 : 6 2 4 5 3 1

    ② i+1 ~ n-1 까지 (i로부터 오른쪽) 범위에서 2보다 큰 첫 번째 수 찾기 : 6 2 4 5 3 1

    ③ swap : 6 2 4 5 3 1 -> 6 3 4 5 2 1

    ④ i+1 ~ n-1 까지 범위의 수 오름차순 정렬 : 6 3 1 2 4 5 = 다음 순열

 

   - 위의 과정을 행하지 않을 경우 : flag=false -> -1 출력

      행한 경우 : flag=true -> num[] 출력

 

 

 

 

10973_이전 순열

10973번: 이전 순열

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] num = new int[n];

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

		boolean flag = false;

		Loop:
		for(int i=n-1; i>=1; i--){
			if(num[i-1]>num[i]){
				flag = true;
				for(int j=n-1; j>=i; j--){
					if(num[i-1]>num[j]){
						int temp = num[i-1];
						num[i-1] = num[j];
						num[j] = temp;

						int k = n-1;
						while(i<k){
							int temp1 = num[i];
							num[i] = num[k];
							num[k] = temp1;
							i++; k--;
						}
						break Loop;
					}
				}
			}
		}

		if(!flag)
			sb.append(-1);
		else{
			for(int i=0; i<n; i++){
				sb.append(num[i]).append(" ");
			}
		}

		System.out.print(sb);
		br.close();
	}
}

 

예) 6 2 4 5 1 3 일때

    ① 오른쪽부터 num[i-1]>num[i] 인 수 찾기 : 6 2 4 5 1 3

    ② i+1 ~ n-1 까지 (i로부터 오른쪽) 범위에서 5보다 작은 첫 번째 수 찾기 : 6 2 4 5 1 3

    ③ swap : 6 2 4 5 1 3 -> 6 2 4 3 1 5

    ④ i+1 ~ n-1 까지 범위의 수 내림차순 정렬 : 6 2 4 3 5 1 = 이전 순열

 

   - 위의 과정을 행하지 않을 경우 : flag=false -> -1 출력

      행한 경우 : flag=true -> num[] 출력