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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

1~N까지의 숫자를 모든 순열을 사전순으로 출력하는 문제

 

 

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 n;
    static int nums[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        n = Integer.parseInt(br.readLine());
        nums = new int[n];
        for(int i=0; i < n; i++){
            nums[i] = i+1;
            sb.append(String.valueOf(i+1)).append(" ");
        }
        sb.append("\n");
        
        while(true){
            boolean result = getNext();
            if(!result) break;
            sb.append(print());
        }
        bw.write(sb.toString());
        bw.flush();
        br.close();
    }
    
    private static boolean getNext(){
        int i = n-1;
        
        // 내림차순이 시작되는 가장 큰 i값을 찾는다.
        while(i > 0 && nums[i-1] >= nums[i]) i--;
        
        if(i <= 0) return false;
        
        // i-1 이후의 모든 숫자 중 큰 것을 고르는데 그 중, j의 값이 가장 큰 경우로 선택
        int j = i-1;
        while(j < n-1 && nums[i-1] < nums[j+1]) j++;
        
        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 = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private static StringBuilder print(){
        StringBuilder sb2 = new StringBuilder();
        for(int num : nums){
            sb2.append(num).append(" ");
        }
        sb2.append("\n");
        return sb2;
    }
}

 

 

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