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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

관련 문제인 다음 순열 문제 포스팅은 여기를 참조

 

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

 

 

현재 주어진 순열의 이전 순열을 구하는 문제

 

 

2. 풀이

 

위 링크의 다음 순열 문제를 풀면서 다음 순열을 구하는 로직을 익힌 적이 있다.

이전 순열 문제를 푸는 방법도 비슷한데, 다음 순열은 특정 i번째 이후의 최종 순열을 i번째 부터의 최초 순열로 바꾸는 것이 다음 순열을 구하는 방법이었다.

그 내용은 다음 접힌 글 또는 상단의 완전 탐색 링크를 참조

※ 순열을 구현하는 방법

현재 순열을 구성하는 배열을 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}

 

 

이전 순열은 그와 반대로, i번째 부터의 최초 순열을 i+1번째 부터의 최종 순열로 만들어 버리면 된다. 방법은 다음과 같다.

 

※ 이전 순열을 구현하는 방법


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


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

2. j >= i 중, A[j] < A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.

  → 현재가 최초 순열 상태이므로 i-1번째 숫자를 변경하여 최종 순열을 찾아야 한다.
      A배열을 기준으로 i-1번째 숫자는 4인데, 그보다 작은 경우는 1, 3이나 그 중 j 값이 가장 큰 경우는 3이다.
      즉, j의 값은 3의 위치인 4가 된다.

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

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

 

 

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 isPrev = get_prev_perm();
        
        if(isPrev){
            for(int num : perm){
                bw.write(String.valueOf(num) + " ");
            }
        } else {
            bw.write(String.valueOf(-1));
        }
        
        bw.flush();
        br.close();
    }
    
    private static boolean get_prev_perm(){
        
        int i = n-1;
        // 뒤에서부터 체크하여 현재 위치부터 오름차순이 시작되는 경우 중, 최대 i값을 구한다.
        // 오름차순이라는 것은 해당 위치 기준으로 뒤의 데이터는 최초 순열이라는 의미이다.
        while(i > 0 && perm[i-1] <= perm[i]) i--;
        
        // 이미 자체적으로 최초 순열이라면, false를 반환
        if(i <= 0) return false;
        
        // j는 현재 i위치에서 시작.
        // i 이후의 모든 숫자 중 i-1번째 보다 작은 것을 고르되, 가장 큰 것을 고른다.
        int j = i;
        while(j < n-1 && perm[i-1] > perm[j+1]) j++;
        
        // j와 i-1번째의 숫자를 swap
        swap(i-1, j);
        
        // 현재 i번째 부터 이후를 내림차순으로 뒤집음. 즉, 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;
    }
}

 

 

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