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

코딩테스트 연습 - 줄 서는 방법 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

정리:

 

 2023.08.08

백트랙킹으로 전체 모든 경우의 수를 보면 시간이 오래 걸리니 정렬했을 때 반복되는 패턴을 찾고 그 패턴이 몇 번 반복되었는지 파악 후에 찾고자하는 번 째의 반복 위치를 찾은 후 그 진행되는 반복 패턴에서의 것 만 계산해서 값을 구하고자 함. 정확성은 모두 맞았으나 효율성은 모두 실패. 추후에 다시 풀 예정 

 

2024.07.11

두 개의 리스트를 활용해서 경우의 수를 따져나가면서 순열을 만드는 식으로 접근해서 풀었다.

 

import java.util.*;
class Solution {
    Set<int[]> set = new HashSet<>();
    public int[] solution(int n, long k) {
        int num = 1;
        for(int i = n - 1; i > 0; i--)
            num *= i;
        int firstn = (int)k / num;
        int fidx = (int)k % num;
        if(fidx != 0)
            firstn++;
        Deque<Integer> queue = new LinkedList<>();

        int l = dfs(n, firstn, queue);
        int[][] arr = new int[set.size()][n];
        int idx = 0;
        for(int[] a : set)
            arr[idx++] = a;
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a , int[] b) {
                for(int i = 0; i < n; i++)
                    if(a[i] != b[i])
                        return a[i] - b[i];
                return a[0] - b[0];
            }
        });
        idx = 0;
        int[] answer = arr[fidx - 1];
        return answer;
    }

    int dfs(int size, int n, Deque<Integer> queue){
        if(queue.contains(n))
            return -1;
        queue.add(n);
        if(queue.size() == size) {
            Deque<Integer> que = new LinkedList<>();
            int[] arr = new int[size];
            int idx = 0;
            while(!queue.isEmpty()){
                int num = queue.poll();
                que.add(num);
                arr[idx++] = num;
            }
            while(!que.isEmpty()) {
                queue.add(que.poll());
            }
            set.add(arr);
            return 0;
        }
        for(int i = 1; i <= size; i++){
            int k = dfs(size, i, queue);
            if(k == 0)
                queue.pollLast();
        }
        return 0;
    }
}

정확성 테스트

테스트 1 〉	통과 (2.33ms, 77.4MB)
테스트 2 〉	통과 (100.72ms, 104MB)
테스트 3 〉	통과 (119.88ms, 103MB)
테스트 4 〉	통과 (2.97ms, 77.2MB)
테스트 5 〉	통과 (1.34ms, 72.5MB)
테스트 6 〉	통과 (0.98ms, 75.7MB)
테스트 7 〉	통과 (19.11ms, 84.6MB)
테스트 8 〉	통과 (2.35ms, 74.5MB)
테스트 9 〉	통과 (3.12ms, 76.4MB)
테스트 10 〉	통과 (871.48ms, 192MB)
테스트 11 〉	통과 (880.29ms, 255MB)
테스트 12 〉	통과 (8366.35ms, 963MB)
테스트 13 〉	통과 (8466.99ms, 1010MB)
테스트 14 〉	통과 (2.52ms, 77.5MB)

효율성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

채점 결과

정확성: 73.7

효율성: 0.0

합계: 73.7 / 100.0

---

import java.util.*;
class Solution {
    ArrayList<Long> list = new ArrayList<>();
    ArrayList<Long> list2 = new ArrayList<>();
    public int[] solution(int n, long ky) {
        int[] visited = new int[n];
        long[] valpocket = new long[n];
        long v = 1;
        for (int i = 1; i <= n; i++) {
            v *= i;
            valpocket[i - 1] = v;
            list2.add((long)i);
        }

        Loop:
        for (int i = n; i > 0; i--) {
            if (i == 1) {
                list.add(list2.get(0));
                break;
            }
            long val = valpocket[i - 1];
            long div = 0;
            if (i != 1)
                div = valpocket[i - 2];
            long cnt = 0;
            cnt = val / div;
            for (long c = 1; c <= cnt; c++) {
                 if (ky <= c * div) {
                     ky -= (c - 1) * div;
                     long temp = list2.get((int)c - 1);
                     list.add(temp);
                     list2.remove((int)c - 1);
                     break;
                 }
            } 
        }

        int[] answer = new int[list.size()];
        int idx = 0;
        for (long num : list)
            answer[idx++] = (int)num;
        return answer;
    }
}

 

정확성 테스트

테스트 1 〉	통과 (0.13ms, 77.7MB)
테스트 2 〉	통과 (0.07ms, 77MB)
테스트 3 〉	통과 (0.10ms, 67.5MB)
테스트 4 〉	통과 (0.05ms, 74.5MB)
테스트 5 〉	통과 (0.06ms, 78.5MB)
테스트 6 〉	통과 (0.05ms, 74.6MB)
테스트 7 〉	통과 (0.08ms, 74.4MB)
테스트 8 〉	통과 (0.07ms, 74.5MB)
테스트 9 〉	통과 (0.05ms, 74.5MB)
테스트 10 〉	통과 (0.12ms, 86.9MB)
테스트 11 〉	통과 (0.09ms, 73.2MB)
테스트 12 〉	통과 (0.08ms, 71.8MB)
테스트 13 〉	통과 (0.08ms, 77.1MB)
테스트 14 〉	통과 (0.07ms, 74.3MB)

효율성 테스트

테스트 1 〉	통과 (0.09ms, 52.6MB)
테스트 2 〉	통과 (0.11ms, 53.1MB)
테스트 3 〉	통과 (0.10ms, 61.2MB)
테스트 4 〉	통과 (0.10ms, 52.1MB)
테스트 5 〉	통과 (0.16ms, 52.6MB)

채점 결과

정확성: 73.7

효율성: 26.3

합계: 100.0 / 100.0