알고리즘 (4) 썸네일형 리스트형 Leetcode in Java - 46. Permutations (backtracking) backtracking이란?backtrack은 `후퇴`로 번역되는데, 미로에서 길을 찾을 때와 같이 막다른 길에 도달하면 마지막 선택으로 돌아가는 것을 말한다. backtracking과 다른 알고리즘의 구별모든 가능성을 전부 탐색해야 하는 brute force 방식으로, 각 탐색이 다른 탐색에 영향을 미치지 않으므로 DP와 다르고, 각 후보(candidate)는 다른 후보와 더 낫거나 모자라지 않으므로, 전역 최댓값을 구하기 위해 국소적 최솟값을 선택하는 greedy와도 구별된다. backtracking 전체적인 흐름 backtracking은 모든 가능한 경우의 수를 탐색하여 최종 답안인 집합 S를 구하게 된다. 후보인 s가 S에 포함될지 안될지를 판단후 포함되면 S에 추가하고, 포함되지 않으면 .. Leetcode in Java - 46. Permutations (재귀) 알고리즘 설명 재귀함수는 depth라는 정수를 매개변수로 받는데, 이 depth는 재귀적으로 함수를 호출할 때마다 1씩 늘어난다. depth에 따라 swap 해주어야 하는 배열의 인덱스가 달라지기 때문이다. swap 해주어야 하는 두 인덱스는 depth와 i인데, i는 depth부터 시작해 배열의 끝(n-1)까지 증가한다. depth가 n과 같아지면 swap하지 않고 최종 반환할 리스트에 추가한다. 코드class Solution { public List> permute(int[] nums) { List> ans = new ArrayList>(); perm(ans, nums, 0); return ans; } public void swap(int[] nu.. 리스트의 리스트 선언하기와 원시타입 배열 리스트로 변환하기 리스트의 리스트 선언하기List> ans = new ArrayList>(); 원시타입 배열을 리스트로 변환하는 법 (Java8 이상)Arrays.stream(arr).boxed().collect(Collectors.toList()); 위장 수정 후import java.util.*;class Solution { public int solution(String[][] clothes) { int answer = 1; HashMap map = new HashMap(); for (int i=0; i values = map.values(); for (Integer val : values) { answer*= (val + 1); } return answer-1; }} 수정 전 - map.size() == 0 일 때 map.get("key") == null (오류 안남)import java.u.. 이전 1 다음
