힙 1문제, 이진 탐색 2문제를 풀었다. 이진 탐색처럼 보이지 않는 문제인데, 이진 탐색이 관련된 태그라서 좀 당황했었다. 그런데 풀어보니 진짜 이진 탐색이 맞더라.. 문제를 봤을 때 실마리가 안 잡히는 경우는 어떻게 하는 게 좋을까?
2300. Successful Pairs of Spells and Potions
양의 정수 배열 spells와 potions가 주어졌다. 배열의 크기는 각각 n, m이고 spells[i]는 i번째 스펠의 세기를 나타내고 potions[j]는 j번째 포션의 세기를 나타낸다. success라는 정수값이 주어졌을 때, 스펠과 포션 쌍의 곱이 success보다 크거나 같을 때 성공적이다(successful)고 한다. pairs[i]는 i번째 스펠이 성공적인 쌍을 형성하는 개수를 나타낸다고 할 때, 길이가 n인 배열 pairs를 리턴하라.
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.
You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.
Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.
이 문제는 이진탐색 문제라는 것이 어느정도 보인다. spells[i]와 potions[j]의 곱이 succes값보다 크거나 같은 potions[j]의 수를 구해야 하는데, potions를 정렬하고 sucess를 넘는 최소 potions[j]를 찾으면, j+1부터 나머지는 계산해보지 않아도 된다. 그런데 spells와 potions의 최대 크기가 10^5이라서 두 값을 곱하는 경우는 overflow가 날 수 있기 때문에, ceil(success / spells[i])한 값을 potions에서 찾는 것으로 대체한다. potions는 중복된 값을 가질 수 있고, ceil(success / spells[i])와 같거나 큰 값이 처음 나오는 경우를 찾아야 하기 때문에 lower bound를 찾아서 리턴한다.
유사한 문제들이 꽤 나오는 것으로 보여서 lower bound, upper bound를 구하는 코드는 연습해서 체득을 해두는 편이 좋을 것 같다.
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
int[] ret = new int[spells.length];
Arrays.sort(potions);
int m = potions.length;
int maxPotion = potions[m-1];
for(int i=0; i<spells.length; i++) {
int minPotion = (int) Math.ceil((1.0 * success) / spells[i]);
if (minPotion > maxPotion) {
ret[i] = 0;
continue;
}
int idx = lowerBound(potions, minPotion);
ret[i] = m - idx;
}
return ret;
}
private int lowerBound(int[] potions, int minPotion) {
int start = 0, end = potions.length;
while(start < end) {
int mid = start + (end - start)/2;
if (potions[mid] < minPotion) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
}알고리즘 성능 분석을 해보자. 길이가 m인 배열을 정렬하는데 필요한 시간은 mlogm, n개의 원소를 순회하면서 lower bound를 찾기 때문에 nlogm이 소요된다. 그래서 시간 복잡도는 O((n+m)logm)이 된다.
공간 복잡도는 배열을 정렬하는데 필요한 공간이 logm이고, 기타 변수를 사용하므로 O(logm)이다. 솔루션을 참고하면 사용하는 언어에 따라 공간복잡도가 달라질 수 있다. 파이썬의 경우는 O(m), C++, Swift, Java, JavaScript는 O(logm)이라고 언급하고 있다.
162. Find Peak Element
peak 요소는 양옆(이웃) 보다 엄격히 큰 값이다. 배열 nums가 주어졌을 때, peak 요소를 찾고 그 인덱스를 리턴하라. 만약에 여러 개의 peak를 찾았다면 그중 하나의 인덱스를 리턴한다.
nums[-1] 이나 nums[n]의 값은 -∞로 가정한다. 즉 배열 바깥의 값은 항상 작다고 가정한다.
O(logn) 시간에 작동하는 알고리즘을 작성하라.
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
이게 왜 binary search 문제인지 이해가 안 됐던 문제. 리트코드 유저가 올려준 솔루션을 읽어보고 나서 어렴풋이 이해가 된 거 같다.
만약 mid 위치의 값이 peak 값이라면, 바로 mid를 리턴하면 된다. 만약 peak가 아니라면, 선택은 두 가지로 나뉘게 된다.
- nums[i] < nums[i-1] 인 경우 : 좌측에 peak 값이 존재할 수 있다. (end = mid-1)
- nums[i] < nums[i+1] 인 경우: 우측에 peak 값이 존재할 수 있다. (start = mid+1)
배열의 길이가 1인 경우, 배열의 양 쪽 끝 원소 등 base case를 먼저 처리하고 이진검색을 하면 답을 찾을 수 있다.
class Solution {
public int findPeakElement(int[] nums) {
if (nums.length==1) {
return 0;
}
int n = nums.length;
if (nums[0] > nums[1]) {
return 0;
}
if (nums[n-1] > nums[n-2]) {
return n-1;
}
int start = 1, end = n-2;
while(start <= end) {
int mid = start + (end - start)/2;
if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid+1]) {
return mid;
} else if (nums[mid] < nums[mid-1]) {
end = mid - 1;
} else if (nums[mid] < nums[mid+1]) {
start = mid + 1;
}
}
return -1;
}
}시간 복잡도는 O(logn), 공간 복잡도는 O(1).
2462. Total Cost to Hire K Workers
배열 costs가 주어졌을 때, costs[i]는 i번째 작업자를 고용하는 비용이다. 두 정수 k와 candidates 또한 주어졌을 때, 다음 룰에 따라 정확히 k 명의 작업자를 고용하려고 한다:
- k회 고용을 하고 한 번에 한 명을 고용한다.
- 각 세션에서 가장 비용이 적게 드는 작업자를 고용하는데, 작업자는 costs 배열 양 쪽 끝에서 candidates 작업자 중에서 뽑는다. 비용이 같다면 인덱스가 작은 작업자를 고용한다.
- candidates 보다 적은 작업자가 남았다면 그중에서 비용이 가장 적은 작업자를 뽑는다.
k 작업자를 고용하는 비용의 합을 구하라.
You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.
You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:
You will run k sessions and hire exactly one worker in each session.In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2]. In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.A worker can only be chosen once.
Return the total cost to hire exactly k workers.
문제 조건을 읽었을 때 잘 이해가 되지 않는다면, 예제를 꼼꼼히 살펴보자. candidates = 4가 어떤 조건인지 잘 이해가 안 됐는데, 첫 번째 라운드에서 양 쪽 끝에서부터 4개의 원소들이 밑줄이 그어져 있다. 이들이 candidates이고 그 중에서 비용이 가장 낮은 작업자를 선택하는 것이다. candidates = 1이라면 후보는 costs[0] = 17, costs[8] = 8 이 후보가 되고 costs[8] = 8이 선택된다.
이 문제는 힙을 통해서 작업자를 선택하면 되겠다는 생각은 들었는데, 다음 라운드에서 candidate를 어떻게 추가할 것인가에 고민이 있었다. 솔루션을 봤을 때 두 개의 우선순위 큐를 사용하는 경우도 있었는데 나는 좌우 포인터(two pointers)를 사용해서 다음 후보를 추가할 수 있도록 하고, 하나의 우선순위 큐를 사용했다.
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
int[][] costIdx = new int[n][2];
for(int i=0; i<n; i++) {
costIdx[i] = new int[]{costs[i], i};
}
PriorityQueue<int[]> pq = new PriorityQueue<>(n, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
});
int l=0, r=n-1;
for(int c=0; c<candidates; c++) {
if (l < r) {
pq.offer(costIdx[l++]);
pq.offer(costIdx[r--]);
} else if (l == r) {
pq.offer(costIdx[l++]);
}
}
long cost = 0;
for(int i=0; i<k; i++) {
int[] costAndIdx = pq.poll();
cost += costAndIdx[0];
if (l <= r) {
if (costAndIdx[1] <= l) {
pq.offer(costIdx[l++]);
} else if (costAndIdx[1] >= r) {
pq.offer(costIdx[r--]);
}
}
}
return cost;
}
}시간 복잡도를 분석해보자. costs 배열의 길이를 n이라고 할 때, costIdx를 생성하는데 필요한 시간은 O(n)이다. 그리고 candidates를 간단히 c라고 하면, 우선순위 큐에 2 * c를 넣어야 하기 때문에 O(clogc)가 소요된다. 그리고 k번 순회하면서 우선순위 큐에서 원소를 빼고 추가하는 작업에 O(klogc)이 소요된다. 따라서 O(n + clogc + klogc) = O(n + (c+k)logc)가 된다.
공간 복잡도는 우선순위 큐에 c개의 원소를 저장하고, costIdx에 n개의 원소를 저장하므로 O(n + c)가 된다.
(최악의 경우를 고려해서 k=n이라면 시간 복잡도는 O(nlogn), 공간 복잡도는 O(n)이 되는 거 아닌가? 알쏭달쏭하다.)
