리트코드 75 17일 차, Array/String 문제 2문제, Backtracking 문제를 한 문제 풀었다. 배열 문제들은 아무리 생각해도 풀 수가 없어서 솔루션을 봤다. 수능 4점짜리 문제를 푸는 기분이랄까? 문제를 풀 수 있는 아이디어가 안 떠오르고 심지어는 솔루션을 봐도 이해가 안 되는 문제가 있다. 이런 문제들은 앞으로 어떻게 연습해야 할지 고민이 된다.
238. Product of Array Except Self
주어진 정수 배열 nums에 대해서 answer[i]는 nums[i]를 제외한 모든 nums의 곱인 answer 배열을 리턴하라. nums의 곱은 모두 32비트 정수임을 보장한다. 나누기를 사용하지 않고 O(n) 시간 복잡도 안에 동작하는 알고리즘을 작성하라.
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
정말 어떻게 풀어야 할지 모르는 문제였는데 솔루션을 보니 좀 허무했다. 알고리즘을 최적의 시간복잡도로 풀어내려면 추가 공간이 더 필요할 수 있다는 생각 하면서 문제를 풀어야겠다.
nums 배열의 길이를 n이라고 할 때 길이가 n인 배열 prefix, suffix를 만든다. prefix[i]는 nums[0]부터 nums[i-1]까지의 곱을 저장하는 배열이고, suffix[i]는 nums[i+1]부터 nums[n-1]까지의 곱을 저장하는 배열이다. 그러면 answer[i] = prefix[i] * suffix[i]가 된다.
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] prefix = new int[len];
int[] suffix = new int[len];
prefix[0] = 1;
suffix[len-1] = 1;
for(int i=1; i<len; i++) {
prefix[i] = prefix[i-1] * nums[i-1];
}
for(int i=len-2; i>=0; i--) {
suffix[i] = suffix[i+1] * nums[i+1];
}
int[] ret = new int[len];
for(int i=0; i<len; i++) {
ret[i] = prefix[i] * suffix[i];
}
return ret;
}
// brute force
// public int[] productExceptSelf(int[] nums) {
// int[] ret = new int[nums.length];
// Arrays.fill(ret, 1);
// for(int i=0; i<nums.length; i++) {
// for(int j=0; j<nums.length; j++) {
// if (i != j) {
// ret[i] *= nums[j];
// }
// }
// }
// return ret;
// }
}이 경우 시간 복잡도는 prefix, suffix 배열을 만들고 answer 배열을 만드는 것까지 O(3n)=>O(n)이 되고, 공간 복잡도도 마찬가지로 O(n)이 된다.
334. Increasing Triplet Subsequence
주어진 정수 배열 nums이 인덱스가 i < j < k 이고 nums [i] < nums [j] < nums [k]인 인덱스를 가지면 true를 리턴하고 아니면 false를 리턴하라.
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums [i] < nums [j] < nums [k]. If no such indices exists, return false.
역시 솔루션을 보고 든 생각. 사람들이 참 똑똑하다. val1, val2를 최댓값으로 초기화한 후, nums 배열을 순회하면서 val1보다 작은 값이 있는 경우 그 값을 val1로 업데이트한다. 그리고 val1보다 크면서 val2보다 작은 경우는 val2값을 업데이트한다. 그리고 val1, val2보다 큰 값이 존재한다면 조건을 만족하게 되므로 true를 리턴한다.
class Solution {
public boolean increasingTriplet(int[] nums) {
int val1 = Integer.MAX_VALUE, val2 = Integer.MAX_VALUE;
for(int n : nums) {
if (n <= val1) {
val1 = n;
} else if (n <= val2) {
val2 = n;
} else {
return true;
}
}
return false;
}
}배열을 한 번만 순회하여 정답을 찾기 때문에 시간 복잡도는 O(n), 변수 2개만 선언하기 때문에 공간 복잡도는 O(1)이다.
216. Combination Sum III
다음 조건을 만족하는 합이 n이 되는 k개 숫자의 조합을 구하라:
- 숫자는 1부터 9까지만 사용 가능하다.
- 각 숫자는 많아야 한 번 사용할 수 있다.
- 모든 유효한 숫자의 조합 리스트를 리턴한다. 중복된 조합은 들어갈 수 없고 순서는 관계없다.
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
candid 배열에 k개 숫자의 조합에 사용할 수 있는 숫자(1부터 9까지)를 저장해 둔다. 1부터 시작해서 숫자의 합이 n이고 ans 리스트의 크기가 k가 되는 경우들을 찾는다. next 값을 ans 리스트에 추가하고 맞는 조합이 있는지 재귀적으로 함수를 호출한 뒤, next 값을 ans 리스트에서 삭제하고 다음 값을 넣어서 Backtracking 방법으로 조합을 구한다.
class Solution {
private int[] candid = {1, 2, 3, 4, 5, 6, 7, 8, 9};
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ret = new ArrayList<>();
combination(ret, new ArrayList<>(), k, n, 0, 0);
return ret;
}
private void combination(List<List<Integer>> ret, List<Integer> ans, int k, int n, int idx, int curSum) {
if (ans.size() == k && curSum == n) {
List<Integer> comb = new ArrayList<>();
for(int num : ans) {
comb.add(num);
}
ret.add(comb);
return;
}
for(int i=idx; i<candid.length; i++) {
int next = candid[i];
if (curSum + next <= n && ans.size()+1 <= k) {
ans.add(next);
combination(ret, ans, k, n, i+1, curSum+next);
ans.remove(ans.size()-1);
}
}
}
} 공간복잡도의 경우, k개 숫자의 조합을 만들어야 하기 때문에 재귀호출이 k번 발생할 것이라서 O(k)가 된다. 시간 복잡도는 최악의 경우, 가능한 모든 조합을 다 시도해 보게 될 것이다. 그래서 1~9까지의 숫자 중 k개 숫자 조합을 검사하는데 C(9, k)가 된다. 따라서 O(C(9, k))가 된다. 리트코드 컨트리뷰션 참고
