백트래킹 문제들

79. Word Search 

https://leetcode.com/problems/word-search/description/?envType=problem-list-v2&envId=backtracking

 

2차원 배열을 순회하면서 word로 주어진 값을 만들 수 있는지 판단하는 문제였다.

현재 좌표에서 동서남북, 4방향으로 이동하는 것도 염두에 둬야 했던 문제였다.

 

39. Combination Sum

https://leetcode.com/problems/combination-sum/description/

 

Input: candidates = [2,3,6,7],
target = 7
Output: [[2,2,3],[7]]

Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

 

중복된 숫자를 포함하며 target을 만들 수 있는 모든 경우의 수를 구하는 문제였다.

 

40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/description/

Example 1:
Input: candidates = [10,1,2,7,6,1,5],
target = 8
Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

 

중복을 허용하지 않으며, target을 만들 수 있는 모든 경우의 수를 구하는 문제.

앞선 문제와 다르게 오름차순을 해줘야 했다.

 

해당 문제를 풀면서 중복된 값을 없애기 위해서 Hash<List<Integer>> 로 된 자료구조에 List<Integer>들을 넣어주었는데, 문제에서 주어진 조건에 의해 시간 초과가 발생했다.

1 <= candidates.length <= 100

 

Set에 넣는다는 것은 결국 모든 경우의 수를 판단해야하기 때문에 최악의 경우 2^100인 시간복잡도가 발생하기 때문에 당연히 시초가 발생한다.

if (i > idx && candidates[i] == candidates[i-1]) continue;

이런 간단한 조건 한줄로 중복되지 않은 원소를 판별할 수 있다.

 

78. Subsets

https://leetcode.com/problems/subsets/description/

 

Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 

주어진 원소들로 만들 수 있는 모든 경우의 수를 구하는 문제였다.

 

90. Subsets II

앞선 문제와 다르게, 중복된 값을 포함하지 않는 선에서 경우의 수를 구하는 문제였다.

나는 HashSet을 사용했는데, 길이 제한이 10이기 때문에 시간 초과가 나지 않아 통과하였다. 

하지만 역시 시간 결과를 보면 하위 80%에 위치한 것을 알 수 있다. 앞선 조건처럼 길이가 더 길었다면 당연히 시초가 발생했을 것이다.

 

46. Permutations

https://leetcode.com/problems/permutations/description/

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input: nums = [0,1]
Output: [[0,1],[1,0]]

 

모든 조합을 계산하는 문제였다. 

[1,2,3] -> [1,1,1] 이런 중복된 원소를 카운팅하면 안되기 때문에 visited 방문 배열을 사용하여 판단했다.

47. Permutations II

https://leetcode.com/problems/permutations-ii/description/

 

위 문제랑 정답이 똑같다.

 

131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

 

이 문제가 조금 까다로웠는데, "aab"를 처음부터 slice를 해가며 팰린드롬인지 판단하는 문제였다.

 

인덱스 시작위치가 제일 헷갈렸는데,

for(int i = idx + 1; i <= s.length(); i++) {
    String sub = s.substring(idx, i);
    ...
}

 

이런식으로 문자열을 잘랐을 때, 

s.substring(0,1)

s.substring(1,2)

s.substring(2,3)

s.substring(1,3)

(2,3), (0,2) (2,3)....

 

이런식으로 우리가 원하는 형태로 자를 수 있게 된다.

재귀를 도는 조건은 해당 sub 문자열이 팰린드롬일 때만 돌게 해주고,

dfs(s, tmp, i);

 

인덱스는 i로 고정시켰다.

 

 

N과 M 시리즈를 푸는 느낌이 들었는데, 아직도 재귀를 시작할 때 시작 인덱스 값이나 재귀를 돌 때 인덱스 처리가 계속 헷갈리는것 같다.

Word Search, Palindrome Partitioning 

요 두 문제를 다시 풀어봐야겠다.