순열, 조합

[WonYong-Jang]

순열

모든 순열 10974 백준 / 다음 순열 10972/ 이전 순열

조합

• nCr ==> n 개의 숫자에서 r개를 뽑는 경우의 수 n 개의 공에서 r개를 뽑는 경우의 수 == n-1개의 공에서 r개를 뽑는 수와 n-1개의 공에서 이미 하나를 뽑았다고 생각하고 r-1개를 뽑는 수를 더한 것과 같기 때문
• 파스칼 삼각형

==> 파스칼 삼각형은 수학에서 이항계수(서로 다른 몇개의 물건 중에 순서없이 물건을 선택할 수 있는 경우의 수)를 삼각형 모양의 기하학적 형태로 배열 한 것

[WonYong-Jang]

Next Permutation

• 다음 순열 구하기 외워서 문제 풀기 문제

==> leetcode 31 Next Permutation

참고

https://www.youtube.com/watch?v=mbOl9qPedDo&list=PL2mzT_U4XxDl8PP-jMk4rt6BPzBtS__pQ&index=25

[WonYong-Jang]

프로그래머스 줄서는 방법

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

• n =3 이고 k = 5 일 때 (5번째 순서 찾기)
• 총 6개를 3으로 나누면 2개씩 3덩어리를 나눌수 있다 (첫번째 자리 구하기)

==> slice = n! / n ==> 3!/3 ==> 2

• 1 로 시작하는 순열 2개, 2로 시작하는 순열 2개, 3으로 시작하는 순열 2개씩 일때 5번째 위치의 첫번째 숫자를 아래와 같이 구하면 2번 인덱스, 즉 첫번째 숫자가 3이라는것을 알수 있다.

• k-1 해주는 이유는 인덱스가 0부터 시작하기 때문

==> (k-1)/slice ==> 4/2 == > 2 (2번 인덱스)

• 이제 3숫자를 제외한 [1, 2] 중에 두번째 오는 숫자를 구하게 되면 다시 처음부터 n =2, k = k % slice 로 시작한다.

이유는 첫번째 숫자가 3이라는 것을 알았고 3으로 시작하는 순열만 보면 되기 때문에 k = 5%6 해주게 되면 0, 1 두개만 보면 된다.( 3으로 시작하는 순열 )

• 위에서 k =k % slice가 0이 나오면 k를 slice로 치환 해준다. (문제 조건에서 k 는 인덱스처럼 0부터 시작하는게 아니고 1부터 시작하므로!)

• 소스코드

class Solution {
    public int[] solution(int n, long k) {
        int[] answer = new int[n]; // 정답 배열 

        if(n ==0 || k ==0) return new int[0];

        ArrayList<Integer> arr = new ArrayList<>();        
        for(int i=0; i< n; i++) { // 초기값 설정
            arr.add(i+1);
        }

        int index = 0;
        long slice = 0;
        while(n > 1) { // n == 1 이 될 때까지 (맨 뒷자리수만 남을 때 까지)
            slice = fac(n) / n;
            int deleteIdx = (int)((k - 1) / slice);
            answer[index++] = arr.remove(deleteIdx);

            k = k % slice;
            if(k ==0) k = slice;     // k 가 0일 경우 slice로 치환
            n--;
        }
        answer[index] = arr.get(0); // 마지막 남은 숫자는 그냥 넣어주기 

        return answer;
    }
    public long fac(long num) {
        if(num <= 1) return num;
        else return num * fac(num-1); 
    }
}

참고 : https://ydeer.tistory.com/61