[완전탐색] permutation sequence

정수 n과 k가 있는데, 1부터 n까지 숫자로 만드는 모든 순열을 나열해서 k번째 순열 구하는 문제

풀이 순서

조합을 찾는 방법은 backtracking 활용, 1부터 시작, 방문 추적함 모든 조합을 구하는 문제이기 때문에

순열을 구하는 공식은 1의 자리, 10의 자리, 100의 자리 이렇게 하나씩 cur에 담아서 구할 수 있도록

cur * 10 씩 곱하고 여기에 현재 들어오는 값 i를 더함 그러면 들어오는 순서대로 한자리씩 커져서 왼쪽에서 오른쪽으로 숫자가 쌓임

 

풀이 시작 1:40

풀이 종료 2:20

다시 풀이

내 풀이

class Solution {
    List<Integer> answer;
    boolean[] visited;
    public String getPermutation(int n, int k) {
        answer = new ArrayList<>();
        visited = new boolean[n+1];
        backtrack(0, n, 0);
        Collections.sort(answer);
        
        return Integer.toString(answer.get(k-1));
    }

    private void backtrack(int cur, int end, int digit) {
        if(digit == end) {
            answer.add(cur);
            System.out.println(cur);
            return;
        }

        for(int i=1; i<=end; i++) {
            if(visited[i]) continue;

            visited[i] = true;
            backtrack(cur * 10 + i, end, digit+1);

            visited[i] = false;
        }
    }
}

다른 사람의 풀이 참고

새로 알게된 사실