8.10

순열

비트 마스킹을 통한 순열 생성 - 정수와 비트연산자 사용

permutation(int cnt, int flag){
	for (int i=0;i<N;i++){
    	// 중복체크
        if((flag & 1<<i !=0) continue;
        numbers[cnt] = input[i]; // 수 선택
        permutation(cnt+1, flag | 1<<i); // 다음 자리수 넘어가기
    }
}

넥스트 퍼뮤테이션.
  - 순열, 조합

넥퍼 사용시 시간복잡도 줄일 수 있다. 1/10
그런데 nPn, nCn 만 가능.

-----

import java.util.Arrays;
import java.util.Scanner;

public class NPTest {
    static int N;
    static int[] map;
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int N = sc.nextInt();
        map = new int[N];
        for(int i = 0; i < N; i++) {
            map[i] = sc.nextInt();
        }
        //0. 입력자료를 오름차순으로 정렬
        Arrays.sort(map);
        //순열이 생성된것이기때문에 while이 아닌 do~while구문
        do {
            System.out.println(Arrays.toString(map));
        }while(np(map));
    }
    
    static boolean np(int[] p) { // 다음 순열을 원하는 기존 순열의 배열
        //1. 맨뒤쪽부터 탐색하며 꼭대기 찾기
        int N = p.length;
        int i = N-1;
        while(i>0 && p[i-1] >= p[i]) { //i>0 조심
            i--;
        }
        if(i == 0) {  // 더 이상 다음 순열을 만들수 없음(가장 큰순열)
            return false;
        }
        //2. 꼭대기 진전(i-1) 위치에 교환할 한단계 큰수를 뒤쪽부터 탐색
        int j = N-1;
        ////i>0 사용 안해도 됨
        while(p[i-1] >= p[j]) { //이 값은 반드시 존재할수 밖에 없음
            j--;
        }
        //3. 꼭대기 직접(i-1)의 위치의 수와 한단계 큰수를 교환 
        swap(p, i-1, j); // i-1번째 주의(i번째 아님)
        
        //4. 꼭대기부터 맨뒤까지의 수를 오름차순의 형태로 바꿈
        int k = N-1;
        while(i < k) { //정렬보다 교환이 유리한 알고리즘 (여긴 i-1 아님)
            swap(p, i, k);
            i++;
            k--;
        }
        return true;
    }
    static void swap(int[] p, int a, int b) {
        int temp = p[a];
        p[a] = p[b];
        p[b] = temp;
    }
}

알고리즘

Swea4012 - 요리사
  - foodB를 구하는 방법 -> A에서 고른 열,행을 전부 0으로.

알고리즘 스터디 - 맵, 셋, 우선순위 큐

우선순위 큐.
  - 트리 맵..? -> 트리 맵. 순서 있다.
  - 람다..?
  - 컴페러터..?
절대값 힙. -> 최대 힙 최소 힙.
char, int 아스키 코드 기준 겹치는거 주의.

맵에 넣을 때 getOrDefault로 새로 넣기.