알고리즘 풀이 - 백준 10972(다음 순열, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

현재 주어진 순열의 다음 순열을 구하는 문제

 

 

2. 풀이

 

이전의 완전 탐색 포스팅에서 순열 관련 내용을 확인하면 더욱 쉽게 풀 수 있다.

다음 순열을 구하는 방법은 완전 탐색 포스팅(상단의 링크 참조)를 통해서도 볼 수 있으니, 그 내용을 참고 부탁드린다.

 

기본적으로 다음 순열을 구하는 로직은 다음과 같다.

※ 순열을 구현하는 방법

현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자. 예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.

아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.

1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)
  → 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음
      A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.

2. j $>=$ i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
  → 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
      A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.

3. A[i-1]과 A[j]를 Swap한다.
   → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 6, 5, 3, 1}

4. i이후의 순열을 모두 뒤집는다.
   → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 1, 3, 5, 6}

 

위 로직을 코드로 구현하여 다음 순열을 구해보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static int perm[];
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        
        perm = new int[n];
        for(int i=0; i < n; i++){
            perm[i] = Integer.parseInt(line[i]);
        }
        boolean isNext = get_next_perm();
        
        if(isNext){
            for(int num : perm){
                bw.write(String.valueOf(num) + " ");
            }
        } else {
            bw.write(String.valueOf(-1));
        }
        
        bw.flush();
        br.close();
    }
    
    private static boolean get_next_perm(){
        int i = n-1;
        
        // 뒤에서부터 체크하여 현재 위치가 뒤에서부터 오름차순이 아닌 경우를 찾음
        // 뒤에서부터 오름차순이라는 것은 사전 순으로 최종 수열이라는 의미임
        while(i > 0 && perm[i-1] >= perm[i]) i--;
        
        // 이미 자체적으로 최종 순열이라면, false를 반환
        if(i <= 0) return false;
        
        // j는 현재 i-1위치에서 시작.
        // i-1 이후의 모든 숫자 중 큰 것을 고르는데 그 중, j의 값이 가장 큰 경우로 선택
        int j = i-1;
        while(j < n-1 && perm[j+1] > perm[i-1]) j++;
        
        // j와 i-1번째의 숫자를 swap
        swap(i-1, j);
        
        // i번째부터 이후의 모든 숫자를 뒤집음
        // i~n-1 사이의 숫자를 상호 뒤집어야 하므로 j 값을 n-1로 초기화
        j = n-1;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
        return true;
    }
    
    private static void swap(int i, int j){
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.