오늘의 학습내용
- 투포인터 vs 이분탐색
- 우선순위 큐
공부한 내용
투포인터와 이분탐색은 모두 탐색하는 과정에서 그 시간 복잡도를 줄여주는데 가장 효율적인 방법이다. 근데 두 방식은 항상 헷갈리기 쉬웠는데 다음과 같이 구분된다.
- 투 포인터 (Two Pointers)
투 포인터는 두 개의 포인터를 사용하여 배열이나 리스트를 탐색하는 방법이다. 일반적으로 한 포인터는 배열의 시작점에 다른 포인터는 끝점에 위치시켜서 두 포인터를 서로 이동시키며 문제를 해결한다.
사용 사례:
- 정렬된 배열에서 특정 조건을 만족하는 두 원소를 찾는 문제.
- 두 수의 합이 특정 값이 되는 쌍을 찾는 문제.
- 구간 합이나 슬라이딩 윈도우 문제에서 사용됩니다.
- 이분 탐색 (Binary Search)
이분 탐색은 정렬된 배열에서 목표 값을 효율적으로 찾기 위한 탐색 방법이다. 배열을 절반으로 나누어 목표 값이 포함된 부분만을 재귀적으로 또는 반복적으로 탐색한다.
사용 사례:
- 정렬된 배열에서 특정 값을 찾는 문제.
- 최적화 문제에서 특정 값을 찾거나 조건을 만족하는 최소 또는 최대 값을 찾는 문제.
- 문제 풀이에서 연속적인 값의 범위를 이분 탐색으로 탐색하여 답을 찾는 경우.
즉 투 포인터는 구간자체를 변화시키면서 접근하는 방식이고 이분탐색은 구간의 크기를 변화시키면서 접근하는 방식이라고 볼 수 있겠다.
오늘의 회고
처음 문제를 확인하고 나서 정렬된 몸무게의 배열에서 우선순위큐로 최대힙과 최소힙으로 구성된 자료구조를 이용해야 한다고 생각했다.
1. 최소힙이 빈칸이 될때까지 다음의 조건문을 반복
1-1. (if) 최소힙의 peek() 와 최대힙의 peek()의 합이 Limit보다 작거나 같으면 answer ++
1-2. (else if) 최소힙에서 제일 작은 수와 두번째로 작은 수의 합이 limit 보다 작거나 같으면 answer ++
1-3. (else if) 1-2의 반례인 경우 answer ++
public static int solution(int[] people, int limit){
int answer = 0;
PriorityQueue<Integer> minPq = new PriorityQueue<>(); // 가장 작은 숫자가 맨 위로
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
int size = people.length;
for(int i=0; i<size; i++){
maxPq.add(people[i]);
minPq.add(people[i]);
}
while(!minPq.isEmpty()){
int min = minPq.peek();
int max = maxPq.peek();
if(minPq.size() > 1) { // pq개수가 둘 이상일떼
if(min + max <= limit){
maxPq.remove(minPq.poll());
minPq.remove(maxPq.poll());
}
int minium = minPq.poll();
int nextMinium = minPq.poll();
minPq.add(minium);
minPq.add(nextMinium);
if(minium + nextMinium <= limit){
maxPq.remove(minPq.poll());
maxPq.remove(minPq.poll());
}else{
maxPq.remove(minPq.poll());
}
}else{
maxPq.remove(minPq.poll());
}
answer++;
}
return answer;
}그러나 최소값과 최대값을 비교한 후 큐에서 처리하는 과정에서 같은 요소를 여러 번 처리하거나 잘못된 값을 제거할 가능성이 있으며 poll과 remove의 조합이 제대로 작동하지 않을 수 있다는 함정이 있었다. 그 결과 위의 시도는 잘못됐고 시간초과까지 불러왔다.
그 이후로 생각해낸 방안은 '투포인터'로 구현하는 것이다. 물론 접근법이 크게 다르지 않지만 우선순위 큐보다 그 복잡도가 더 적고 큐로써 크기가 마음대로 변하지 않기 때문에 더욱 안정적인 방법이었다.
문제
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
내 풀이
- 사람들의 몸무게 배열을 정렬한다.
- 가장 가벼운 사람과 가장 무거운 사람을 쌍으로 묶어 구명보트에 태울 수 있는지 확인한다.
- 두 사람의 무게 합이 보트의 무게 제한을 넘지 않는다면, 두 사람을 함께 보트에 태운다. 그렇지 않으면 가장 무거운 사람만 태운다.
- 반복하여 모든 사람을 구출할 때까지 과정을 진행한다.
public int solution(int[] people, int limit) {
Arrays.sort(people); // 사람들의 몸무게를 정렬
int i = 0, j = people.length - 1;
int answer = 0;
while (i <= j) { // 두 포인터가 만나거나 교차할 때까지
if (people[i] + people[j] <= limit) {
i++; // 가장 가벼운 사람을 태움
}
j--; // 가장 무거운 사람을 태움
answer++; // 구명보트 하나 사용
}
return answer;
}다른 사람 풀이
반복문에서 항상 틀에 맞춰서 구현했는데 아래와 같이 자유분방한 풀이도 있었다! 뭔가 투포인터로 구현한 것과 유사하지만 결국엔 수학적 계산이 기반한 후에 좀더 깔끔하게 구현된 것 같다.
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
Arrays.sort(people);
int i = 0, j = people.length - 1;
for (; i < j; --j) {
if (people[i] + people[j] <= limit)
++i;
}
return people.length - i;
}
}
