자바 코딩테스트 강좌, 순열의 순서 구하기

문제 정의

주어진 숫자 배열에서, 특정 숫자의 순열을 구했을 때 그 순열이 몇 번째에 위치하는지를 구하는 문제입니다. 예를 들어, 배열이 [1, 2, 3]일 때, 모든 순열을 나열하면 아래와 같습니다:

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

예를 들어, 숫자 2의 경우, 순열이 2, 1, 3일 때, 이 순열은 3번째에 위치하게 됩니다. 우리는 이러한 정보를 바탕으로 주어진 숫자의 순열이 몇 번째인지 알아낼 것입니다.

문제 접근 방법

이 문제를 해결하기 위해 다음과 같은 단계를 따르면 됩니다:

1. 주어진 배열의 길이를 바탕으로 총 순열의 개수를 계산합니다.
2. 주어진 타겟 순열을 기준으로 필요한 공식을 통해 각 단계에서 몇 번째인지 계산합니다.
3. 순서 계산을 위한 재귀 함수를 작성하여 각 단계별로 순열의 순서를 찾아냅니다.

순열의 개수 계산

주어진 숫자 배열의 길이를 n이라고 할 때, n! (n 팩토리얼) 개의 순열이 존재합니다. 이는 1부터 n까지의 모든 정수를 곱한 값입니다.

예를 들어, 배열의 길이가 3이라면 순열의 개수는 3! = 6입니다.

순서 계산을 위한 음수화와 재귀

순서를 계산하기 위해서는 특정 숫자가 선택된 이후의 경우를 고려해야 합니다. 예를 들어, 우리가 1을 선택한다고 가정하면, 그 이후로 남은 숫자들로 이루어진 순열의 경우를 재귀적으로 호출하여 순서를 계산합니다.

이러한 접근법으로 각 숫자별로 몇 개의 순열이 가능한지를 찾아내 계산을 수행합니다.

자바 코드 구현

아래는 “순열의 순서 구하기” 문제를 해결하기 위한 자바 코드입니다:

public class PermutationOrder {
    
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3}; // 주어진 배열
        int[] target = {2, 1, 3};   // 순서 계산할 타겟 순열
        int rank = findRank(numbers, target);
        System.out.println("타겟 순열의 순서: " + rank);
    }
    
    public static int findRank(int[] numbers, int[] target) {
        int n = numbers.length;
        boolean[] used = new boolean[n];
        return getRank(numbers, target, used, 0);
    }
    
    private static int getRank(int[] numbers, int[] target, boolean[] used, int index) {
        int rank = 1; // 기본 순서는 1부터 시작
        int n = numbers.length;
        
        for (int i = 0; i < n; i++) {
            // 타겟 숫자보다 작은 경우
            if (!used[i]) {
                for (int j = 0; j < target[index]; j++) {
                    if (j == numbers[i]) {
                        break;
                    }
                    rank += factorial(n - index - 1); // (n-1)! 만큼 추가
                }
            }
            if (target[index] == numbers[i]) {
                used[i] = true; // 해당 숫자를 사용함
                break;
            }
        }
        
        if (index < n - 1) {
            rank += getRank(numbers, target, used, index + 1); // 다음 인덱스를 위해 재귀 호출
        }
        
        return rank;
    }

    private static int factorial(int n) {
        if (n == 0) return 1;
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}
            

이 코드에서는 주어진 숫자 배열과 목표 순열을 기반으로 순서를 계산하기 위해 재귀적 접근법을 사용합니다. 주요 함수 getRank는 점진적으로 타겟 순열에서 각 숫자를 검사하고, 다른 숫자들과의 조합에 따라 순서를 결정합니다.

예제 테스트 케이스

코드를 작성한 후 다음과 같은 여러 예제를 통해 결과를 검증할 수 있습니다:

• 입력: [1, 2, 3], 타겟: [2, 1, 3] → 출력: 3
• 입력: [1, 2, 3], 타겟: [1, 3, 2] → 출력: 2
• 입력: [1, 2, 3], 타겟: [3, 2, 1] → 출력: 6

위의 코드로 다양한 배열과 타겟 순열을 실험하여 올바른 출력을 얻기까지 얼마든지 반복할 수 있습니다. 순열의 조합만으로도 다양한 테스트 케이스가 생성 가능하므로, 알고리즘의 정확성과 효율성을 따져봐야 합니다.

결론

이번 글에서는 자바를 활용하여 순열의 순서를 구하는 문제를 다루어 보았습니다. 재귀적인 접근 방식과 순열의 개수 계산, 그리고 정확한 순서 확인을 위한 알고리즘이 결합해 문제를 효과적으로 해결할 수 있었던 점을 강조하고 싶습니다. 이를 통해 코딩 테스트에 대한 이해도가 높아지고 보다 다양한 문제를 해결하는 데 큰 도움이 되길 바랍니다.