[백준] code.plus(브루트포스-순열,JAVA)10973번, 이전 순열

문제 링크

10973번: 이전 순열

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

순열이란

n개의 원소를 중복없이 나열하는 것입니다.

순열 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 오름차순으로 이루어진 순열이다.

2. 1~N개의 수로 이루어져있다.

3. 입력값 이전에 오는 순열 값을 구해라.

 

문제를 순서대로 풀었다면 10972번 다음 순열을 풀어보았을 것이라고 생각합니다.

저는 10972번에서 사용한 next_permutation을 활용하여 이전 순열을 구하는 알고리즘을 작성하였습니다.

아래 링크는 10972번을 제가 해결한 내용으로 next_permutation에 대한 내용을 포함하고 있습니다.

[백준] code.plus(브루트포스-순열,JAVA)10972번, 다음 순열

 

 

배열

cur  : 입력된 현재 순열의 값

 

cur과 previous-permutation을 이용하여 입력 순열에 다음 순열을 구하였습니다.

 

next-permutation이란?

순열의 다음 값을 구하기 위한 알고리즘입니다.

1. 현재 순열의 값 뒤에서부터 역순이 아닌 순서쌍을 찾습니다.(해당 순서쌍에 큰 값의 위치를 point라고 하겠습니다.)

2. 뒤에서부터 point-1번째 값보다 큰 값을 찾습니다.(큰 값의 위치를 change라고 하겠습니다.)

3. point-1의 값과 change의 값을 서로 바꾸어줍니다.

4. point~순열의 끝의 범위를 reverse를 진행해줍니다.

 

previous-permutation이란?(next_permutation을 응용하여 작성하였습니다)

순열의 다음 값을 구하기 위한 알고리즘입니다.

1. 현재 순열의 값 뒤에서부터 역순인 순서쌍을 찾습니다.(해당 순서쌍에 큰 값의 위치를 point라고 하겠습니다.)

2. 뒤에서부터 point-1번째 값보다 작은 값을 찾습니다.(작은 값의 위치를 change라고 하겠습니다.)

3. point-1의 값과 change의 값을 서로 바꾸어줍니다.

4. point~순열의 끝의 범위를 reverse를 진행해줍니다.

 

위 과정을 예를 들어 표현해보겠습니다.

현재 순열이 {2, 1, 3, 4}일 때(위치는 0부터 시작합니다.)

 

1. 뒤에서부터 역순인 순서쌍을 찾는다.

(3,4) = 역순이 아닌 순서쌍

 

(1,3) = 역순이 아닌 순서쌍

 

(2,1) = 역순인 순서쌍

 

순서쌍의 작은 값(1)의 위치 point = 1

 

2. 뒤에서부터 point - 1 = 1 - 1 = 0번째 값(2)보다 작은 값을 찾습니다.

2 > 4 = X

 

2 > 3 = X

 

2 > 1 = O

 

작은 값(1)의 위치 change = 1

 

3. point - 1의 값과 change의 값을 서로 바꾸어줍니다.

0번째 값과 1번째 값을 변경한 순열은 {1, 2, 3, 4}입니다.

 

4. point ~ 순열의 끝의 범위를 reverse를 진행해줍니다.

1~3의 범위를 reverse를 진행한 순열은 {1, 4, 3, 2}입니다.

 

결과적으로 {2, 1, 3, 4}의 다음 순열은 {1, 4, 3, 2}으로 표현할 수 있습니다. 

 

※1번 과정에서 순서쌍을 찾지 못한다는 것은 현재 순열이 오름차순으로 이루어져있다고 판단하여 이전 순열을 존재하지 않습니다.

 

문제에 해결알고리즘은 previous_permutation을 구현하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer을 사용하여 현재 순열의 값을 배열에 저장하였습니다.
• previous_permutation 알고리즘을 수행하는 previousPermutation 함수를 만들었습니다.
• 배열의 값을 변경하는 swap함수를 만들었습니다.
• previousPermutation의 결과에 따라 이전 순열의 값이나 -1을 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• nextPermutation는 과정1~4을 point와 change을 사용하여 이전 순열이 존재하면 구하고 없으면 false를 반환하도록 구현하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;
	public static int[] cur;	//현재 순열 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-------입력값 저장 및 배열 초기화---------
    	N = Integer.parseInt(br.readLine());
    	cur = new int[N];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++) {
    		cur[i] = Integer.parseInt(st.nextToken());
    	}
    	if(previousPermutation()) {		//이전 순열 존재 여부 확인
    		for(int i=0;i<N;i++) {
    			bw.write(cur[i] + " ");		//존재시 이전 순열 BufferedWriter 저장
    		}
    	}else
    		bw.write("-1");		//없을 시 -1 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //-----이전 순열 구하는 함수-----
    public static boolean previousPermutation() {
    	int point = -1;
    	for(int i=N-1;i>0;i--) {	//조건 1.
    		if(cur[i-1]>cur[i]) {
    			point = i;
    			break;
    		}
    	}
    	if(point == -1)		//조건1에서 순서쌍 찾지 못하였을 때, 이전 순열 존재 X
    		return false;
    	
    	int change = -1;
    	for(int i=N-1;i>=point;i--) {	//조건 2.
    		if(cur[point-1]>cur[i]) {
    			change = i;
    			break;
    		}
    	}
    	swap(point-1, change);	//조건 3.
        
    	change = N-1;
    	while(point<change) {	//조건 4.
    		swap(point,change);
    		point++;
    		change--;
    	}
    	return true;
    }
    //------배열 값 교환하는 함수-------
    public static void swap(int x, int y) {
    	int temp = cur[x];
    	cur[x] = cur[y];
    	cur[y] = temp;
    }
}