[ 알고리즘 ] Next Permutation ( with 백준 10972 )

Next Permutation

→ 현 순열에서 사전 순으로 다음 순열 생성

→ 입력 받은 배열을 오름차순으로 정렬 후 구한다.

→ 주로 do-while문이 사용

 

 

next permutation이 필요한 상황

데이터가 537으로 들어왔을 때 사전순으로 순열을 만들면 4개밖에 나오지않는다.

실제 나와야하는 값은 6개가 나와야한다.

 

 

next permutation을 사용해 다음 순열 구하는 방법

- 오름차순에서 내림차순으로 순열을 모두 뽑아내고 싶으면 처음엔 꼭 미리 오름차순 정렬하기 - 

 

예시) 10 3 9 8 7 6 5 2 1 의 다음 순열 찾기 [ 해당 데이터는 배열에 들어있다고 가정 ]

1. 꼭대기 인덱스 찾기 [ 꼭대기란 ? 뒤에서부터 탐색하여 처음으로 감소하는 수의 전 숫자의 인덱스 ]
    - 해당 예시에선 9가 꼭대기

    - [ top = N(데이터 개수)-1 = 배열의 끝]로 초기화 후

       1) top이 0보다 크고 top - 1 > top인 경우 top--를 한다 → 앞의 데이터가 더 큰 수이기에 top의 인덱스를 줄이기

       2) top이 0보다 크고 top-1<top인 경우 break한다.

 

2. 꼭대기 바로 앞의 데이터와 swap할 데이터 찾기

    - swap할 데이터는 꼭대기 뒤의 데이터들에서 꼭대기 앞의 데이터보다 큰 데이터들 중 가장 작은 데이터

 

 

3. 꼭대기부터 뒷 부분 오름차순 정렬

    - 정렬 방법

              → sort함수 사용
              → 양쪽 끝을 시작으로 짝을 지어 변경

                       

 

 

 

---

 

 

NP를 연습해볼만한 문제로는 백준의 10972. 다음 순열이 있다.

10972번: 다음 순열

 

 

특정 순열이 주어지면 해당 순열 다음에 오는 순열을 구하는 문제로 코드는 다음과 같이 작성했다.

import java.util.*;

public class BJ_10972 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);	//입력을 받기 위해 Scanner 객체 생성
        int N = sc.nextInt();					//순열의 길이 입력받기
        int arr[] = new int[N];					//순열을 담을 배열 선언
        for (int i = 0; i < arr.length; i++) {	//현재 순열의 정보 담기
            arr[i] = sc.nextInt();
        }
        //1번 꼭대기 구하기
       	int top = N - 1;				//top을 맨 뒤의 값으로 지정
        while (top > 0 && arr[top - 1] > arr[top]) { 	//top보다 더 큰 수가 앞에 존재할 경우
            top--;					// 꼭 top>0이 먼저 들어가야 인덱스 오류 발생이 안일어난다.
        }
        if (top == 0) {					//이미 내림차순일 경우
            System.out.println(-1);
            System.exit(0);
        }
        
        //2번 스왑할 위치 찾고 스왑하기
        for (int i = arr.length - 1; i >= top; i--) {
            if (arr[i] > arr[top - 1]) {
                swapIndex = i;
                break;
            }
        }
        // 아래 코드도 가능
        // while (arr[top - 1] > arr[swapIndex]) {
        // swapIndex--;
        // }
        
        int tmp = arr[top - 1];
        arr[top - 1] = arr[swapIndex];
        arr[swapIndex] = tmp;
        
        //3번 top이후 데이터들끼리 오름차순 정렬
        Arrays.sort(arr, top, arr.length);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

 

 

 

 

---

 

참고자료

공룡 좋아하는 언니(지인) 의 기깔나는 NP 설명😎