프로그래머스 - 줄 서는 방법 JAVA :: 12936

문제 링크

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

---

문제 이해하기

순서대로 완전 탐색을 할 수도 있겠지만 (물론 시도해 봤지만) 시간초과가 발생합니다.

그래서 패턴을 찾아보는 것으로 생각을 바꿨습니다.

• 경우의 수
  

  

  n=3 경우의 수

  
  

  

  n=4 경우의 수

  
  우선 경우의 수 구하는 방법은 n! 입니다.
  $3! = 3*2*1 = 6$
  $4! = 4*3*2*1 = 24$

• 공식 유도
  n=4에서 15번째 수를 구해보겠습니다.
  15번째 수는 [3,2,1,4] 입니다.
  그러나 배열은 0부터 시작이므로 k=14로 계산을 시작합니다.

• 첫 번째 수 구하기
  

  

  (1)

• 두 번째 수 구하기
  

  

  (2)

• 세 번째 수 구하기
  

  

  (3)

• 네 번째 수는 4만 남았으므로 생략하겠습니다.

• 공식은 위와 같고 코드로 풀어보겠습니다.

문제 풀이

1번 풀이

    

      
      
      
      
    
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        List<Integer> list = new ArrayList<>();

        long f = 1;
        for(int i=1; i<=n; i++) {
            list.add(i);
            f *= i;
        }

        k--; 
        int idx = 0;
        while(idx < n) {
            f /= n - idx;
            answer[idx++] = list.remove((int) (k / f));
            k %= f;
        }

        return answer;
    }
}

• 핵심 코드
  

  

정확성 테스트

테스트 1 〉	통과 (0.03ms, 77.2MB)
테스트 2 〉	통과 (0.03ms, 74.7MB)
테스트 3 〉	통과 (0.04ms, 72.4MB)
테스트 4 〉	통과 (0.04ms, 78.1MB)
테스트 5 〉	통과 (0.04ms, 75MB)
테스트 6 〉	통과 (0.04ms, 76.6MB)
테스트 7 〉	통과 (0.03ms, 83.6MB)
테스트 8 〉	통과 (0.04ms, 74.4MB)
테스트 9 〉	통과 (0.03ms, 75.7MB)
테스트 10 〉	통과 (0.03ms, 74.4MB)
테스트 11 〉	통과 (0.03ms, 78.4MB)
테스트 12 〉	통과 (0.05ms, 78.6MB)
테스트 13 〉	통과 (0.03ms, 83.1MB)
테스트 14 〉	통과 (0.03ms, 71.8MB)

효율성 테스트

테스트 1 〉	통과 (0.06ms, 52MB)
테스트 2 〉	통과 (0.06ms, 51.9MB)
테스트 3 〉	통과 (0.06ms, 52.2MB)
테스트 4 〉	통과 (0.06ms, 51.9MB)
테스트 5 〉	통과 (0.05ms, 52.1MB)

---

실패한 풀이

1번 풀이(시간초과)

    

      
      
      
      
    
public class Solution {
    long k, count = 0;
    int[] answer;
    public int[] solution(int n, long k) {
        this.k = k;
        answer = new int[n];
        int[] arr = new int[n];
        int[] output = new int[n];
        boolean[] visited = new boolean[n];
        for(int i=0; i<n; i++) { arr[i] = i+1; }

        perm(arr, output, visited, 0, n);

        return answer;
    }

    public void perm(int[] arr, int[] output, boolean[] visited, int depth, int n) {        
        if(depth == n) {            
            this.count++;
            if(this.k == this.count) {
                for(int i=0; i<n; i++) { this.answer[i] = output[i]; }
            }
            return;
        }

        if(this.k == this.count) return;

        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                perm(arr, output, visited, depth + 1, n);
                visited[i] = false;
            }
        }
    }
}

2번 풀이(시간초과)

    

      
      
      
      
    
import java.util.Stack;

public class Solution {
    long k;
    int[] arr;
    boolean[] visit;
    Stack<Integer> st;

    public int[] solution(int n, long k) {
        st = new Stack<>();
        arr = new int[n]; 
        visit = new boolean[n]; 

        long fact = 1;
        for(int i=1; i<=n; i++) { fact *= i; }
        long gap = (fact / n);
        int start = (int) Math.ceil((double)k / (fact / n)) - 1;

        int num = 1;
        for(int i=1; i<n; i++) {
            if(num == start+1) { num++; }
            arr[i] = num++;
        }
        arr[0] = start+1;
        this.k = k - (start * gap);    

        perm(n);
        while(!st.empty()) { arr[--n] = st.pop(); }

        return arr;
    }

    public void perm(int n) {        
        if(st.size() == n) {
            this.k--;
        } else {
            for(int i=0; i<n; i++) {
                if(this.k == 0) break;

                if(!visit[i]) {
                    visit[i] = true;
                    st.push(arr[i]);
                    perm(n);
                    if(this.k == 0) break;
                    st.pop();
                    visit[i] = false;
                }
            }
        }
    }
}

---