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

문제 링크

10972번: 다음 순열

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

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

 

순열이란

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

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

 

이 문제에 핵심은

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

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

3. 입력값에 다음에 오는 순열 값을 구해라.

 

처음 문제를 해결할 때에는 재귀문을 사용하여 모든 순열의 경우의 수를 구하고 boolean형을 이용하여 입력값과 동일한 경우의 수가 나오면 다음 경우의 수를 출력하도록 하였습니다.

하지만 결과는....... '시간 초과'가 발생하였습니다.

배열을 여러개 써보기도 하면서 진행해보았지만 '메모리 초과'가 발생하였습니다.

여러가지 시도를 해보았지만 실패하여 구글링을 시작하였으며 제가 참고한 곳을 올려두겠습니다.

next_permutation 알고리즘

위에 링크에 나온 next_permutation을 사용하여 이번 문제를 해결하였습니다.

 

배열

cur  : 입력된 현재 순열의 값

 

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

 

next-permutation이란?

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

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

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

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

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

 

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

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

 

1. 뒤에서부터 역순이 아닌 순서쌍을 찾는다.

(4,1) = 역순

 

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

 

순서쌍의 큰 값(4)의 위치 point = 3

 

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

1 < 3 = X

 

4 > 3 = O

 

큰 값(4)의 위치 change = 3

 

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

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

 

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

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

 

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

 

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

 

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

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer을 사용하여 현재 순열의 값을 배열에 저장하였습니다.
• next_permutation 알고리즘을 수행하는 nextPermutation 함수를 만들었습니다.
• 배열의 값을 변경하는 swap함수를 만들었습니다.
• nextPermutation의 결과에 따라 다음 순열의 값이나 -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());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	cur = new int[N];
    	for(int i=0;i<N;i++) {
    		cur[i] = Integer.parseInt(st.nextToken());
    	}
    	if(nextPermutation()) {		//다음 순열이 존재하는지 확인
    		for(int i=0;i<N;i++) {
    			bw.write(cur[i] + " ");	//다음 순열 BufferedWriter 저장
    		}
    	}
    	else
    		bw.write("-1");	//다음 순열 존재 안할 시 -1 BufferedWriter 저장
    	bw.flush();		//결과 저장
    	bw.close();
    	br.close();
    }
    //-----next_permutation 알고리즘 함수-------
    public static boolean nextPermutation() {
    	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;
    	return;
    }
}