20220214 APS 응용 순열

비교연산자

Comparable

• 자신과 인자로 전달 받는 타 원소와 비교하여 정수 리턴
  • 음수 결과 : 타 원소가 크다 x.compareTo(other)
  • 0 결과 : 둘이 같다
  • 양수 결과 : 자신이 크다

Comparator

• 비교 대상의 두 원소가 아닌 별도의 도우미 역할
• 두 원소(o1, o2) 비교하여 정수 리턴
  • 음수 결과 : o2 원소가 크다
  • 0 경과 : 둘이 같다
  • 양수 결과 : o1 원소가 크다

순열 (Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 nPr

순열을 생성하는 방법

1. 반복문을 통한 순열 생성 : 순열의 갯수가 적을때, 순열의 길이가 변동이 없을때
2. 재귀 호출을 통한 순열 생성 : boolean[ ] 사용
3. 비트마스킹을 통한 순열 생성 : 정수와 비트연산자를 사용
4. 현 순열에서 사전 순으로 다음 순열 생성 ( NextPermutation )
   • 배열을 오름차순으로 정렬한 후 시작
   • 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성
     1. 뒤쪽부터 탐색하며 교환위치 ( i-1 ) 찾기 ( i:꼭대기 )
     2. 뒤쪽부터 탐색하며 교환위치 ( i-1 )와 교환할 큰 값 위치 ( j ) 찾기
     3. 두 위치 값 ( i-1, j ) 교환
     4. 꼭대기위치 ( i ) 부터 맨 뒤까지 오름차순 정렬

package com.ssafy.bit;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class NextPermutationTest {
	static int N, input[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		input = new int[N];
		for(int i=0;i<N;i++)
			input[i]=sc.nextInt();
		
		// 1. 오름차순 정렬
		Arrays.sort(input);
		
		do {
			// 순열 출력
			System.out.println(Arrays.toString(input));			
		}while(np());
		
	}
	private static boolean np() {
		
		// 1. 교환위치 찾기
		int i = N-1;
		while(i>0 && input[i-1]>=input[i])
			--i;
		if(i==0)
			return false;
		
		// 2. 교환위치에 교환할 값 찾기
		int j = N-1;
		while(input[i-1]>=input[j])
			--j;
		
		// 3. 교환위치와 교환할 값 교환하기
		swap(i-1, j);
		
		// 4. 교환위치 뒤(꼭대기)부터 맨 뒤까지 만들수 있는 가장 작은 순열 생성 (오름차순정렬)
		int k=N-1;
		while(i<k)
			swap(i++, k--);
		
		return true;
	}
	
	public static void swap(int i, int j) {
		int temp=input[i];
		input[i]=input[j];
		input[j]=temp;
	}
}

비트 연산자

• & : 비트단위로 AND 연산
• | : 비트단위로 OR 연산
• ^ : 비트단위로 XOR 연산 ( 같으면 0, 다르면 1 )
• ~ : 단항 연산자로서 피연산자의 모든 비트를 반전
• << : 피연산자의 비트 열을 왼쪽으로 이동
• >> : 피연산자의 비트 열을 오른쪽으로 이동 ( 부호비트로 좌측을 채움 )
• >>> : 피연산자의 비트 열을 오른쪽으로 이동 ( 0으로 좌측을 채움 )