👀 문제
https://leetcode.com/problems/permutations/
👊 도전
1. 설계
- DP를 이용한다.
- i 위치에서 건너뛸 수 있는 max를 구하고, 1~max까지 뛰어본다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
*
* @author HEESOO
*
*/
class Solution {
int n;
boolean[] visit; // 사용 여부 체크
List<List<Integer>> result;
public List<List<Integer>> permute(int[] nums) {
n=nums.length;
visit=new boolean[n];
result=new ArrayList<List<Integer>>();
permutation(new ArrayList<Integer>(), nums);
return result;
}
public void permutation(ArrayList<Integer> list, int[] nums){
if(list.size()==n){ // 순열 생성 완료
result.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<n;i++){
if(visit[i]) continue; // 사용한 숫자는 패스
visit[i]=true;
list.add(nums[i]);
permutation(list, nums);
list.remove(list.size()-1); // 재귀를 끝내고 다시 돌아온 후, 다음 사용을 위해 원상복구
visit[i]=false;
}
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 재귀를 이용해 순열을 구한다
- 순열은 순서를 고려한다.
- visit[] 배열을 둬서 숫자 사용 여부를 체크한다. 이를 통해 중복을 거른다.
- for문에서 0부터 n까지 숫자를 확인한다. visit[i]가 true면 사용한 숫자이므로 패스한다.
- 사용하지 않은 숫자는 true로 바꾸고, list에 넣은 후 다시 permutation()을 재귀 호출한다. 이렇게 해서 n개의 숫자를 고른다.
- n개를 다 골랐으면 result에 넣는다. 이때 result.add(list)를 하면 리스트 내에 빈 값만 들어간다. 따라서 위와 같이 작성해야 한다(이유는 아직 이해가 안된다).
- 재귀를 끝나고 재귀 호출 다음으로 돌아오면, 방금 넣었던 nums[i]를 지금 선택하지 않는 경우를 위해 list에서도 삭제, visit에서도 false로 바꾼다. 다음 사용을 위함이다.