순열

 

 

 

 

 

오늘 LG CNS 코딩테스트를 쳤다. 3문제 중에 2문제는 테스트 케이스를 통과했고 1문제는 풀지 못했다.

아마도 문제가 전부 쉬워서 떨어질 것 같긴하다.

2번째 문제를 푸는데 dfs로 잘 안풀려서 고민하다가 마지막 20분 전에 순열로 풀 수 있는 방법이 떠올라서 열심히 했는데 시간 내에 완성하지 못하고 그냥 제출했다. 

 

순열은 그냥 dfs나 브루트포스처럼 전부 계산하면 되긴 하지만 시간 제한 때문에 조금 알고리즘을 알아두면 좋을 것 같다.

밑에 다음 순열을 구하는 알고리즘은 오늘 시험과는 무관하지만 그냥 순열을 공부하다보니 자주 등장하길래 한번 정리해봤다.

 

 

 

백준 - 다음 순열

 

int i = 배열 마지막 인덱스,

int j = 배열 마지막 인덱스 일때

1. i > 0 이면서 A[i] > A[i-1]를 만족하는 카장 큰 i를 찾는다.

2. A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다.

3. A[i-1]과 A[j]를 swap한다.

4. A[i]부터 순열을 뒤집는다.

 

뭔가 직관적인 알고리즘은 아닌 것 같다. 고등학교 때 배운적이 없어서 그런지 처음에는 간단해보이지만 생각하는데 조금 시간이 들었다.

 

 

예를 들어 

 

1 5 2 4 3 을 입력을 넣으면 (1), (2) 과정을 거치면서

 

i는 3이고 j는 4이 된다.

 

(3) 과정을 거치면 1 5 3 4 2 가 된다.

 

마지막으로 (4) 과정을 거치면 1 5 3 2 4 가 된다.

 

숫자 5개로 하면 뭔가 직관적이지 않다.

 

 

조금 더 쉬운 이해를 위해 더 큰 입력을 넣는다. 

7 1 5 6 4 3 2

 

i, j는 각각 3, 3이 된다.

 

(3)과정을 거치면 7 1 6 5 4 3 2 가 된다.

(4) 과정을 거리면 7 1 6 5 4 3 2이 된다.

 

계속 시도하다 보면 규칙이 보인다.

 

 

 

 

 

---

백준 - 다음 순열

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int i = n - 1;
        int j = n - 1;
        // 과정 (1)
        while (i > 0 && arr[i - 1] >= arr[i]) {
            i--;
        }
        if(i == 0) {
            System.out.print(-1);
            return;
        }
        
        // 과정 (2)
        while (arr[i - 1] >= arr[j]) {
            j--;
        }
        
        // 과정 (3)
        swap(arr, i - 1, j);

        // 과정 (4)
        int j = n - 1;
        while (i < j) {
            swap(arr, i, j);
            i += 1;
            j -= 1;
        }

        for (int l = 0; l < n; l++) {
            System.out.print(arr[l] + " ");
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}