[프로그래머스] 줄서는 방법 - Java

https://programmers.co.kr/learn/courses/30/lessons/12936?language=java 

코딩테스트 연습 - 줄 서는 방법

오늘은 프로그래머스의 Level3의 연습문제 중 하나인 줄 서는 방법 문제를 풀어보았다.

처음 시도에는 브루트포스 방법을 사용했지만, 효율에서 터져서 어떠한 방법으로 풀어볼까 고민하다가 수학적으로 풀어보려고 노력했다.

숫자의 사전식 순서로 배열하기 때문에 간단하게 코드를 짤 수 있었다.

 

문제에선 n값과 k값을 받는데 n은 사람의 수이고, k는 사람을 줄세우는 k번째 방법을 나타낼 때 사용하는 값이다.

사람의 범위가 20명밖에 되지 않기 때문에 가장먼저 범위를 줄일 수 있도록 하는 factorial 배열을 만들었다.

import java.util.*;
class Solution {
    static boolean[] visited = new boolean[21];
    static ArrayList<Integer> arr = new ArrayList<>();
    static int[] answer;
    static long[] factorial = new long[21];
    public int[] solution(int n, long k) {
        if(n==1) return new int[]{1};
        
        factorial[0] = factorial[1] = 1;
        for(int i = 2; i < n; i++){
            factorial[i] = i * factorial[i-1];
        }
        
        answer = new int[n];
        go(n,0,k);
        return answer;
    }
}

 

아래는 범위를 좁힐 수 있도록 하는 go 메소드의 코드이다.

가장 우선 사전식 배열이기 때문에 1부터 n까지의 for loop을 진행한다. 여기서 번째 수에 해당하는 범위를 넘지 않는 선에서

반복적으로  n에서 깊이 만큼 뺀 factorial값을 빼준다.

이때 k의 값이 0이되거나 그것보다 작다면 그 값을 시작값부터 그 이후의 값으로 선택된다.

만약 k==0이미지만 depth의 값이 마지막값과 같지 않다면 앞에서부터 차례대로 값을 배열에 넣어준다.

여기서  visited 배열을 통해 같은 값이 들어가지 않도록 중복 체크를 꼭 해줘야한다.

public void go(int n, int depth, long k){
        if(k == 0) {
            if(depth < n){
                for(int i = 1; i<=n; i++){
                    if(visited[i]) continue;
                    answer[depth++] = i;
                }
            }
            return;
        }
        for(int i = 1; i<=n; i++){
            if(visited[i]) continue;
            if(k - factorial[(n-1)-depth] <= 0) {
                visited[i] = true;
                answer[depth] = i;
                go(n,depth+1,k);
            }
            else {
            	k -= factorial[(n-1)-depth];
            }
        }
    }

이 문제는 중학생의 경우의 수 문제를 코드로 활용한 문제여서 수학적 풀이 방법으로 풀어보았다.

통과 결과이다.

다만 factorial을 사용하는데 그 범위가 커지면 사용하기 어려울 것이다.