👀 문제
https://leetcode.com/problems/combination-sum/
👊 도전
1. 설계
- 이분탐색을 이용해 target을 하나 찾는다.
- 만약 target을 찾지 못한다면 {-1,-1}을 리턴한다.
- target이 있다면, 그곳을 기준으로 left, right를 두고 target이 아닌 값을 만날 때 까지 움직인다.
- left의 최소, right의 최대를 리턴한다.
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
37
38
39
40
/**
*
* @author HEESOO
*
*/
class Solution {
HashSet<List<Integer>> set;
int[] c;
int t;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
set=new HashSet<>();
Arrays.sort(candidates);
c=candidates;
t=target;
combination(0, "");
return new ArrayList(set);
}
public void combination(int sum, String str){
if(sum==t){ // sum 완성
ArrayList<Integer> list=new ArrayList<>();
String[] array=str.split(" ");
for(String s:array) { // 생성한 str를 list 형태로 변환
if(s.equals("")) continue;
list.add(Integer.parseInt(s));
}
Collections.sort(list);
set.add(list);
return;
}
for(int i=0;i<c.length;i++){ // 조합 찾기
if(sum+c[i]>t) return; // t보다 크면 다음은 볼 필요도 없으므로 종료
combination(sum+c[i], str+c[i]+" ");
}
}
}
3. 결과
🤟 성공 🤟
그닥 좋은 코드는 아닌듯😭 i가 무조건 0부터 체크하고, str를 다시 list로 바꾸고, 오름차순 정렬하는 데에서 시간이 소요되는 것 같다.
4. 설명
- 모든 조합을 다 찾는다
- 이때 숫자는 중복으로 쓸 수 있으므로 파라미터로 시작 인덱스를 넘기지 않고 무조건 0부터 순회하게 했다(다른 사람들의 풀이를 보니 사용한 i를 다시 start로 넘겨 중복으로 쓸 수 있게 했다. 이게 더 나은 듯).
- 현재까지의 합계 sum에 넣을 값 c[i]가 t를 넘는다면 다음 숫자들은 볼 필요도 없으므로 return한다(이를 위해 c를 오름차순 정렬한 후 사용했다).
- 숫자 생성에 성공하면 지금까지 만든 str를 list형태로 변환하고, set에 넣어 중복을 거른다.