순열이란?
서로 다른 n개중에 r개의 숫자를 순서를 고려 해서 뽑는 경우를 말합니다.
순열의 정의를 아는 것을 가정하에 프로그래밍을 하기전에 사전조사 작업을 해볼 필요성이 보입니다
1. 길이 n만큼의 배열이 필요합니다
2. n개의 배열중 r개를 뽑을수있게끔 길이 r만큼의 배열이 필요합니다
3. 뽑았을때 중복여부를 판단할수있는 boolean 함수가 필요합니다
사전조사 작업을 끝마쳤으니 프로그래밍 시점으로 순열을 알아봅시다
카드 5장 중에서 4장을 뽑는다고 가정과 동시에, 4장을 각각의 졸라맨으로 치환하겠습니다.
1. 순열은 순서가 중요하지만 중복을 싫어합니다.
졸라맨[R개]들은 모든 칸을 다 만지고 싶어한다
- 졸라맨은 모든칸을 선택할수있는 권한은 존재한다.
- 와 같은 그림이 있다고 사용했을때, 중복없이 4개를 골라 나열해본다고 생각해보자.
- 첫번째 졸라맨은 a~f를 모두 선택할수 있고
- 두번째 졸라맨, 세번째 졸라맨 또한 a~f를 선택할 수있다.
- 이런 문제점들은 [a,b,c,e]에서 중복적인 선택을 할수밖에 없다.
- 하지만 순열은 중복도 될수도없고, 순서또한 중요하다.
2. 중복을 피하기 위해선 어떻게 해야하나?
- 하나의 확인 배열을 만드는것이다.
- 1번졸라맨은 a~f을 다 만질수있으니 a를 먼저 가져갑니다
- 확인배열 인덱스에도 True [ 나 방문했어 ] 를 선언합니다
- 1번졸라맨은 1번 인덱스만 보면되니 졸라맨의 역할은 끝난것이다. 그리고 다음 졸라맨을 호출하는것입니다.
- 만들어진 2번 졸라맨도 a~f을 다 만질수있습니다.
- 하지만 2번 졸라맨은 1번째 배열에 누군가 방문했다라는 표시를봅니다.
- 그렇다면 2번 졸라맨은 그 다음 인덱스(b~f)을 보는것입니다..
오케이...그럼 졸라맨들이 꽉 채워져있으면 끝나는건가?
- 절반은 맞고 절반은 틀리다.
- 각 졸라맨들의 임무는 모든칸들을 만지고싶어하는것이다.
- 4번째의 졸라맨은 모든칸들을 만져야 하기때문에 지금 만진 칸을 버린다.
- 지금 만진칸을 버린다는것은 false처리하고 다음칸[ d → e] 을 가는것이다.
❗오해하지마!!!!!!!!!!!!!! [제일 중요]
- 중복을 피하기위한 방문배열 필요
- 한 졸라맨이 모든칸까지 가지않았고, 자신이 할당이안되어있는 상태라면? ⇒
- 자신 인덱스에 맞춰서 변수를 할당받고, 방문처리를 해줍니다.
- 다음 칸을 만지기위해서 for문으로 이동
- 한졸라맨이 모든칸까지 가지 않았고, 할당되어있는 변수가 있다면? ⇒
- 모든 졸라맨이 칸을 다 채울때까지 기다린 다음, 자신의 차례가 된다면 할당되어있는 것을 해제해줍니다.
- 그다음 졸라맨은 반복문 또는 재귀를 통해서 채워야할 다음칸으로 이동합니다.
import java.util.Arrays;
public class Test01_perm {
//N은 used 또는 cars 개수
//R은 N개중 R개를 뽑기때문에 R을 설정
static int N=4 , R=3;
static String[] cards = {"A","B","C","D"};
//방문 배열 선언
static boolean[] used = new boolean[N];
//실제로 R개를 추출하기위해서 만든배열
static String[] result = new String[R];
public static void main(String[] args) {
//항상 인덱스는 1번째부터 생각하기때문에 0을 삽입
perm(0);
}
static void perm(int idx) { // result의 idx칸에 집착함. R개를 채워야돼!!!!
if(idx==R) { //R개가 채워졌다면?
System.out.println(Arrays.toString(result));
return;
}
for(int i=0; i<N; i++) { //카드의 종류는 여러개가있다
if(used[i]) continue; //내 선배 재귀가 카드를 먼저 찜했네... 그건 제끼고 다음카드 보자
result[idx]=cards[i]; // 오 사용가능한 i번 카드가 있네 ? 가져가자
used[i]=true; //난 카드 가져갔으니까 다음 졸라맨은 참고하도록!!
perm(idx+1); //다음 내 후배 졸라맨 너도 0번부터 카드 다 새로봐야한다.
used[i]=false; //R개를채웠으니 졸라맨이 N개를 또봐야하니까 일단 내가 갖고있는건 해제하고
//다음 카드가 있는지 봐야지~~~
}
}//end for perm method
}