[1,2,3,4] 라는 리스트가 있을 때, 해당 리스트에서 2개의 길이로 뽑아낼 수 있는 조합 모두 구하기
**List<Integer> myList = new ArrayList<>() // 1,2,3,4가 들어있는 리스트다**.
-먼저, 이중 for문을 통해 푸는 데 조합을 이중리스트에 담아서 풀어본다
List<List<Integer>>answer = new ArrayList<>();-> 2개를 뽑을 조합을 담을 이중리스트
for(int i=0; i<myList.size(); i++){
for(int j=i+1; j<myList.size(); j++{ ->i가 0번째 위치해있을 때 j는 1번째 위치부터 선택해야 중복으로 뽑는 경우를 막는다.
List<Integer> temp = new ArrayList<>(); -> 2개의 조합을 anwer내부에 있는 리스트에 담아야하니까 answer리스트 안의 리스트가 될 temp리스트를 만든다.
temp.add(myList.get(i)); ->temp에 myList.get(인덱스)메서드를 통해 myList의 값을 가지고온다
temp.add(mtList.get(j)); ->temp에 myList의 j번째 요소까지 추가한다.
answer.add(temp); -->그러면 위에서 i=0일때, j=1일때 temp={1,2}가 되고 이걸 answer에 추가하면 answer={{1,2}}상태가 된다.
} -->그러면 반복문을 다 돌면 answer에는 {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}의 제대로 된 조합이 추가된다.
}
-----------------------------------------------------------------------------------------------------
**그런데 이 때, temp리스트를 반복문 바깥에다 선언하면 내부 for문이 돌때 temp가 계속해서 초기화되어야 하는데
초기화 되지 않고 temp에 add되었던 모든 값들이 저장되어 answer에는 제대로 되지 않은 조합들이 저장된다.
그럼에도 불구하고, temp리스트를 반복문 바깥에다 선언해보자.(백트래킹 공부를 위해)
**List<Integer> myList = new ArrayList<>() // 1,2,3,4가 들어있는 리스트다.**
List<Integer> temp = new ArrayList<>();
for(int i=0; i<myList.size(); i++){
temp.add(myList.get(i));
for(int j=i+1; j<myList.size();j++{
temp.add(myList.get(j));
answer.add(new ArrayList<>(temp));----------------------
temp.remove(temp.size()-1) //첫 번째 백트래킹
}
temp.remove(temp.size()-1) //두 번째 백트래킹
}
예를 들어보자.
i=0일 때, 먼저 temp={1} 들어가고 j=1부터 시작하게 되니 temp={1,2}가 된 상태에서!
answer에 add되면서 answer에는 첫 값으로 {1,2}가 적절하게 들어간다.
그리고 i가 여전히 0인 상태에서 j=2가 될 때 temp.add(myList.get(2))가 되면서
temp에는 3이 들어가는데 만약 백트래킹을 하지 않았다면 우리가 원하는temp={1,3}이 아닌
{1,2,3}이 되어버린다. 왜냐하면 temp는 현재 내부 for문 바깥에 있는 상태라 j=1에서 2로 되어도,
값이 초기화 되지 않고, temp={1,2}가 그대로 남아있고 그 상태에서 3값이 추가되니 말이다.
그래서 내부 for문에서 answer에 temp를 추가하고 나면!
temp의 끝에 자리값을 삭제해준다.
다시 i=0,j=1일 때로 돌아가 생각하면 temp={1,2}가 answer에 add 되었고
j=2일때 {1,3}의 정확한 답을 만들기 위해 add된 다음 temp의 끝자리를 삭제해주는 것이다.(이것이 백트레킹!)
그렇게 j가 끝까지 다돌고 바깥 for문으로 돌아가기 직전이 되면
즉, i=0인 상태에서 j=3일 때 {1,4}가 적절하게 answer에 들어갔을 것이고
그 다름 끝 짜리도 삭제 되었을 테니 temp = {1}이 된다.
그런데 바깥 for문으로 가면 즉 i=1이면 temp에는 먼저 2값이 담겨야하는데
이때도 백트래킹하여 끝자리를 삭제해주지않으면 j가 마지막일 때 남겨진 1값이 그대로 저장되어
바깥 for문에서 temp={1,2}인채로 내부 for문 돌때의 값을 추가하게 되므로
두 번째 백트래킹 까지도 필요한 것이다.
---------------------------------------------------------------------------------------------------------------------------
** 앞에서는 문제에서 2개를 뽑아 조합을 만들라고 했기에 우리는 for문을 2번만 만들면 되었다.
하지만, 우리가 몇개를 뽑아 조합을 만들지 모를때, 즉 n개로 문제에서 주어질때 우리는 이 방법으로
풀 수 없고, 재귀함수와 백트래킹을 이용하여 해결해야한다.
**List<Integer> myList = new ArrayList<>() // 1,2,3,4가 들어있는 리스트다**.
List<List<Integer>>answer = new ArrayList<>();
List<Integer>temp = new ArrayLisr<>();
Solution(answer,temp,myList,2,0)->매개변수로 2는 문제에서 주어진 뽑아야할 개수고,
0은 메서드 내에서 for문을 돌때 index를 위한 것으로 항상 0으로 입력해주어야한다.
==메서드 부분==
1번.
public static void Solution(List<List<Integer>> answer, List<Integer>temp, List<Integer> myList
int n, int index,){
-->먼저 필요한 인자값이다. 최종값을 저장할 이중리스트answer, 이중리스트 내부의 리스트가 될 temp,
우리가 뽑아야할 숫자들이 들어있는 myList, 몇 개를 뽑아야 할 지에 대한 정보인 n, 그리고 index.
if(temp.size() == n){
answer.add(new ArrayList<>(temp));------------------------
return;
}
-->for문의 인덱스 설정이 까다로운데 이중for문에서 바깥쪽 for문이 0부터 돌면 내부for문이 1부터
돌아가야하는 것처럼 for문과 재귀호출 될for문의 인덱스가 1씩 차이나야한다.
그 방법이 매개변수로 for문의 i에 대입할 0값을 입력받고 내부 for문의 역할을 할
재귀함수를 호출할 때는 i+1을 한다.
for(int i=index; i<myList.size(); i++){
temp.add(myList.get(i));
solution(answer,temp,myList,n,i+1){
temp.remove(temp.size()-1);
}
-->작동원리
먼저 메서드를 실행하면 temp는 main메서드에서 생성만해놓은 상태일 것이니 사이즈가 0으로 if문을
타지 않고 for문으로 간다. 이때 i=0(외부에서 매개변수로 0값을 입력해야함)
그러면 i=0 일 때, temp에 먼저 1값이 추가된 뒤 solution(answer,temp={1},myList,n,1(i+1))인
재귀호출(이때 상태 1이라 가정)!
제일 처음 if문에서 temp사이즈 =1이니 아래 for문으로 이동하면 재귀i=1부터 시작해서 myList의 사이즈 4미만까지 실행해야 함
그러면 temp에 2추가 되어 temp={1,2}인 상태(상태a)에서 또 재귀호출하는데 if문에서 길이 2로 answer에
현재의 {1,2}만 저장된 채 리턴되어 전에 상태(상태a)로 돌아옴. 그리고 solution에서 리턴된 상태이니
remove 실행하여 temp={1}
그리고 재귀i=2가 되어 temp={1,3}에서 또 재귀호출을 하나 if문에서 answer에 저장만한채 리턴.
또 마지막 자리를 삭제하여 temp={1}이 되고 재귀i=3이 되어 temp={1,4}된 후, 재귀호출하나
answer에 저장만하고 리턴. 그런다음 끝짜리 삭제하면{1} 그런데 재귀 i=1~3까지 반복을 다 돌았다.
그러니 temp={1}만 남긴체 상태 1에서 호출한 재귀가 완료!!
그러면 i=0일때의 상태 1로 돌아가는 것이다. 그러면 재귀호출을 완료했으니 다음에
temp.remove로 마지막 자리수를 삭제하니 temp={}빈값이 되어버린다. 그리고 i=1일때 for문을 돌면
temp={2}가 저장 그리고 다시 재귀호출!(상태2)
이때 호출한 재귀는 solution(answer,temp={2}인상태,myList,n,2(i+1이니까))
그리고 이 호출된 재귀 i=2부터 3까지 돌면
answer={2,3}과 {2,4}가 저장. 재귀호출이 끝나면 상태 2로 돌아와
temp={}가 다시 빈값이 되고 i=2일 때 temp={3}(상태3)
재귀호출하여 재귀i=3일때 for문 돌아{3,4} answer={3,4}저장.
i=3일 때 temp={4}그리고 solution의 인덱스가 4인상태로 재귀호출하는데
재귀i가 4부터 시작할 수없으니 다시 돌아오고 temp={4}도 끝자리 삭제로 빈값이 되고
i=0~3까지 반복문 다돌게 되면서 최종적으로 종료...!
1,2,3,4가 들어있는 리스트에서 순서 상관없이 2개를 뽑는 순열문제라고 생각해보자
**List<Integer> myList = new ArrayList<>() // 1,2,3,4가 들어있는 리스트다**.
List<List<Integer>> answer = new ArrayList<>();
List<Integer> temp = new ArratList
Solution(myList,answer,temp,2,new boolean[myList.size())
//매개변수로 boolean타입의 배열을 넣어야하는데 매개변수에서 바로 생성
//이 논리 배열은 아래 메서드에서 각 인덱스자리를 방문했냐 안했냐로 사용되기 때문에 크기는 myList
//의 size로 설정한다
==메서드 부분==
public static void Solution(List<Integer> myList, List<List<Integer>> answer, List<Integer>temp
,int n,boolean[] visited)
if(temp.size()==n){
answer.add(new ArrayList<>(temp));
return;
}
for(int i=0; i<myList.size(); i++){
if(visited[i]==false){
visited[i] == true; //백트래킹
temp.add(myList.get(i));
Solution(myList,answer,temp,n,arr);
temp.remove(temp.size()-1);
visited[i] == false; //백트래킹
}
}
--> 처음에는 temp의 사이즈가 없으므로 바로 for문이 실행된다. 매개변수에서 생성된 boolean
배열은 처음에 false값으로 초기화되어있으므로 i=0일 때, visited[i]=false로 for문 진입한다.
그리고 곧바로 visited[0]=true로 바꾸어 주는데 이는 i=0일때 for문을 돌았다는 의미다.
그러면 temp에 1값이 추가된 다음 재귀호출(myList,answer,temp{1},n,arr{T,F,F,F})한다.
temp=1값을 가진채 재귀i가 0~3까지 반복문 돌아야한다.
그러고 반복문은 위의 조합과 비슷하게 진행된다. 차이점이 있다면
위에는 인덱스를 재귀호출되는 인덱스를 원래 인덱스보다 +1하여 내껄 뽑으면 다음거부터 뽑게할 수있게했고
여기서는 순열이니까 재귀호출되는 인덱스도 다시 0부터 시작하여 나를 기준으로 전에것도 뽑게 한다.
그러면 문제점이 같은 인덱스 즉 나를 2번이나 뽑을 수 있다는 것인데
그거를 visited[]배열로 방지.