[프로그래머스 5단계] 알고리즘 40. 줄 서는 방법

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 40. 줄 서는 방법

N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.

이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에... 서 있는 상태를 나타냅니다.

이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.

예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.

• 1번째 방법은 [1,2,3]
• 2번째 방법은 [1,3,2]
• 3번째 방법은 [2,1,3]
• 4번째 방법은 [2,3,1]
• 5번째 방법은 [3,1,2]
• 6번째 방법은 [3,2,1]

이 때 K가 5이면 [3,1,2]가 그 방법입니다.

사람의 수 N과 순서 K를 입력받아 K번째 방법으로 줄을 세우는 setAlign 함수를 완성해 보세요. 예를 들어 setAlign(3,5)를 입력받는다면 [3,1,2]를 리턴해주면 됩니다.

import java.util.Arrays;

class LineCombination {

    public int[] setAlign(int n, long k) {

        int[] answer = {};

        return answer;

    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.

    public static void main(String[] args) {

        LineCombination lc = new LineCombination();

        System.out.println(Arrays.toString(lc.setAlign(3, 5)));

    }

}

풀이:

나의 알고리즘은 다음과 같다.

1. 1, 2, ..., n을 원소로 가지는 리스트와 길이가 n인 배열을 하나씩 만든다.

2. factor라는 변수에 팩토리얼 계산을 통해 해당 자리수가 가질 수 있는 경우의 수를 저장한다.

3. 리스트에서 k/fact 인덱스의 요소를 삭제하고 그 요소를 배열에 저장한다.

4. k에 k%fact를 저장한다.

5. n에서 1을 뺀다. 

6. n > 0 조건을 만족시킬때까지 2~5를 반복한다.

이 알고리즘을 코드로 나타내면 다음과 같다.

public int[] setAlign(int n, long k) {

//1. 리스트와 배열을 만든다.

List<Integer> list = IntStream.rangeClosed(1, n)

.boxed()

.collect(Collectors.toList());

int [] answer = new int[n];

int idx = 0;

k-=1;

while(n > 0){

long factor = factorial(n-1);                //2. 해당 자리 수가 가질 수 있는 경우의 수 저장

int index = (int)( k / factor );              //3. 인덱스 계산

answer[idx++] = list.remove(index);    //3. 해당 인덱스의 요소 삭제와 동시에 배열에 순서대로 넣는다.

k %= factor;                                    //4. 다음 자리수를 검사하기 위해 나머지 연산을 한다.

n-=1;                                             //5. n을 1 빼고 6. 이를 반복한다.

}

return answer;

}

팩토리얼 함수에 대한 설명은 생략한다. 이 문제의 핵심은 순열이다. n명이 줄을 설 수 있는 방법은 n! 가지가 있다. 예시의 n=3일때 경우의 수를 생각해보자.

• 첫 번째 자리의 수를 선택하는 경우의 수 : 1, 2, 3 중 하나. 즉 경우의 수는 3가지.

• 두 번째 자리의 수를 선택하는 경우의 수 : 첫 번째 자리 수를 제외한 나머지 2개 중 하나. 즉 경우의 수는 2가지.

• 세 번째 자리의 수를 선택하는 경우의 수 : 첫, 두 번째 자리 수를 제외한 나머지 1개 중 하나. 즉 경우의 수는 1가지.

이제 n! 방법 중 k번째 줄 서는 방식을 고르는 것을 생각해보자. 이 부분에서 제일 중요한 점은 문제에서 줄 서는 방식 k번째라는 것은 우리가 생각하는 배열 인덱스와 차이가 나서 연산이 어긋난다는 것이다. 따라서 연산 시작 전에 k에서 1을 빼주는 것이 포인트이다. 그러면 문제에서 경우의 수의 인덱스를 다시 생각해보자

• 1, 2, 3 -> 0번째

• 1, 3, 2 -> 1번째 

• 2, 1, 3 -> 2번째

• 2, 3, 1 -> 3번째

• 3, 1, 2 -> 4번째 

• 3, 2, 1 -> 5번째

이기 때문에 따로 더 연산을 생각할 필요가 없다. (실제로 필자가 이 문제를 월요일부터 풀었는데 지금에서야 올리는 이유이다. 분명 생각한 알고리즘이 맞는거 같은데 미묘하게 연산이 틀려서 에러를 일으키고 있었다) 

먼저 문제의 예에 대해서 나의 알고리즘을 적용하여 풀어보자. k=5이다. 연산에 따라 k를 1빼준다. 즉 k=4이다.(첫 번쨰 줄 서는 방식은 0이라는 것을 잊지말라!)첫번째 수를 선택했을 때 나머지를 줄 세우는 경우의 수는 (n-1)!가 있다. 즉 선택한 수는 해당 자리에서 가질 수 있는 경우의 수를 품고 있다. 

• 첫번째 자리의 수를 1로 선택했을 때 : 0, 1번째 방식을 포함하고 있다.

• 첫번째 자리의 수를 2로 선택했을 때 : 2, 3번째 방식을 포함하고 있다.

• 첫번째 자리의 수를 3로 선택했을 때 : 4, 5번째 방식을 포함하고 있다.

따라서 k / (n-1)! = 4 / (2)! = 2는 리스트에서 선택할 수를 반환하는 인덱스이다.

만약 3을 골랐다면 0~3번째 경우의 수를 확인한 것이니 이제 4, 5번째 줄 서는 방식만 검사하면 된다. 그 다음을 어떻게 검사하냐면 k에 k%(n-1)!을 저장하고 이를 반복하면 된다. 문제의 예를 들어보자. 3은 이미 선택되어 있다. 남은것은 리스트에서 1, 2 에서 줄 세우는 경우의 수는 다음과 같다.

 

• 1, 2 -> 3을 고른 선택에서 0번째(4 + 0)

• 2, 1 -> 3을 고른 선택에서 1번째(4 + 1)

에서 선택하는 것이다. 즉 k=0이 저장되어 있고 두 번째 자리 수를 선택하는 방법은 (2-1)! 0/1 이니까 인덱스 0을 고르게 된다. 따라서 3, 1, 2를 반환하게 된다.  5단계에 들어서니까 문제의 답을 찾기가 점점 어려워지고 있다. 다른 사람의 문제 풀이나, 인터넷을 뒤져봐도 10번정도 실행하면 오답이 나와서 난감했다는... 이제 5단계도 1문제 남았다 파이팅!