💡 문제
징검다리(https://school.programmers.co.kr/learn/courses/30/lessons/43236)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
1. 정렬
정렬은 데이터를 특정 순서대로 나열하는 작업입니다. 이 문제에서는 바위의 위치를 오름차순으로 정렬해야 하므로 정렬 알고리즘에 대한 이해가 필요합니다. Java에서는 기본적으로 Arrays.sort() 메서드를 사용할 수 있습니다.
2. 이분 탐색 알고리즘
이분 탐색은 정렬된 배열에서 특정 값을 찾거나, 특정 조건을 만족하는 값을 찾는 데 사용됩니다. 이 문제에서는 가능한 최소 거리의 최댓값을 찾기 위해 이분 탐색을 사용합니다.
- 이분 탐색의 기본 원리: 정렬된 배열의 중간 값을 선택하고, 목표 값이 중간 값보다 작거나 크면 탐색 범위를 절반으로 줄이는 방식입니다.
- 이분 탐색 구현 방법: 반복문을 사용한 구현, 재귀를 사용한 구현
- 이분 탐색의 시간 복잡도: O(log n)
3. 그리디 알고리즘
그리디 알고리즘은 매 순간 가장 최적인 선택을 함으로써 최선의 해결책을 찾는 알고리즘입니다. 이 문제에서는 현재 최소 거리를 설정하고, 이를 유지하기 위해 바위를 제거하는 방식으로 접근합니다.
🤓 문제 풀이
🔨 문제 설명
이 문제는 이분 탐색과 그리디 알고리즘을 활용하여 해결할 수 있습니다. 목표는 바위를 n개 제거한 후, 남은 바위들 사이의 최소 거리 중 최대 값을 찾는 것입니다. 이를 위해 다음과 같은 접근 방법을 사용할 수 있습니다.
먼저 바위의 위치를 정렬합니다. 이렇게 하면 바위 간의 거리를 계산하기가 쉬워집니다. 그 다음, 가능한 최소 거리의 최댓값을 찾기 위해 이분 탐색을 사용합니다.
이분 탐색을 진행하면서 현재 중간 값(mid)을 최소 거리로 설정하고, 이를 만족하도록 바위를 제거할 수 있는지 확인합니다. 만약 바위를 제거할 수 있다면, mid 값을 높여 더 큰 최소 거리의 최댓값을 찾습니다. 그렇지 않다면 mid 값을 낮춰 탐색 범위를 줄입니다.
이 문제의 본질은 "바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값"을 찾는 것입니다. 최적화 문제로, 특정 조건을 만족하는 최대/최소 값을 찾는 문제는 이분 탐색을 통해 효율적으로 해결할 수 있습니다.
🔨 접근 방법
- 바위의 위치를 정렬합니다.
- 최소 거리의 최댓값을 찾기 위해 이분 탐색을 합니다.
- 현재 중간 값(mid)을 최소 거리로 설정하고, 이 값을 유지하기 위해 제거해야 하는 바위의 수가 n개 이하인지 확인합니다.
- 만약 제거해야 하는 바위의 수가 n개 이하라면, 현재 중간 값을 최소 거리의 후보로 간주하고 더 큰 값을 탐색합니다. 그렇지 않다면 더 작은 값을 탐색합니다.
🔨 문제 풀이 과정
- 범위 설정:
- 최소 거리의 최솟값(left)을 1, 최대값(right)을 거리의 최대값(distance)로 설정합니다.
- 중간값 설정 및 검증:
- 중간값(mid)을 계산하여 현재 mid를 최소 거리로 설정했을 때, 제거해야 하는 바위의 수가 n개 이하인지 확인합니다.
- 조건을 만족하면 mid값을 저장하고 더 큰 값을 탐색하여 최댓값을 찾습니다.
- 조건을 만족하지 않으면 더 작은 값을 탐색합니다.
🔨 이분탐색 선택 이유
최적화 문제로, 특정 조건을 만족하는 최대/최소 값을 찾는 문제는 이분 탐색에 적합합니다.
"최솟값 중 가장 큰 값"과 같은 표현이 나오면 이분 탐색이 적합한 접근 방식일 가능성이 높습니다. 이런 문제들은 최적화 문제로, 특정 조건을 만족하는 최대값이나 최소값을 찾는 것이 목적입니다. 이분 탐색은 이러한 범위 기반 문제를 해결하는 데 매우 효율적입니다.
바위의 개수가 최대 50,000개이고, 거리 범위가 1부터 1,000,000,000까지입니다. 이 문제를 단순히 모든 가능한 거리를 계산하여 해결하면 매우 비효율적입니다. 이분 탐색을 사용하면 탐색 범위를 절반으로 줄여 효율적으로 최적화를 찾을 수 있습니다.
이분 탐색은 정렬된 범위 내에서 특정 값을 찾거나 특정 조건을 만족하는 값을 찾는 데 매우 유용하여 문제에서 최솟값 중 최대값을 찾는 것은 특정 값을 기준으로 조건을 만족하는지 확인하는 과정에서 이분탐색을 통해 효율적으로 수행할 수 있습니다.
- 최적화 문제:
- 문제에서 "최솟값 중 가장 큰 값" 또는 "최댓값 중 가장 작은 값"을 찾는 경우는 일반적으로 최적화 문제입니다.
- 이분 탐색은 특정 조건을 만족하는 최적의 값을 빠르게 찾는 데 적합합니다.
- 조건 만족 여부 확인:
- 이분 탐색을 통해 중간 값을 설정하고, 그 값을 조건으로 설정하여 문제를 풀어가는 방식이 효율적입니다.
- 각 단계에서 조건을 만족하는지 확인하고, 범위를 좁혀가며 최적화 찾습니다.
🔨 구현코드
1) 이분탐색+그리디로 풀이한 코드
import java.util.Arrays;
class Solution {
public int solution(int distance, int[] rocks, int n) {
Arrays.sort(rocks); // 바위들을 정렬합니다.
int left = 1; // 최소 거리의 최솟값
int right = distance; // 최소 거리의 최댓값
int answer = 0; // 결과를 저장할 변수를 초기화합니다.
while (left <= right) { // 이분 탐색을 수행합니다.
int mid = (left + right) / 2; / 중간 값을 구합니다.
int removed = 0; // 이전 바위의 위치를 나타내는 변수를 초기화합니다.
int prev = 0; // 제거한 바위의 개수를 나타내는 변수를 초기화합니다.
// 바위를 제거하여 가능한 최대 거리를 구합니다.
for (int rock : rocks) {
if (rock - prev < mid) { // 현재 바위와 이전 바위 사이의 거리가 mid보다 작으면
removed++; // 바위를 제거합니다.
} else { // 그렇지 않으면
prev = rock; // 현재 바위를 새로운 위치로 업데이트합니다.
}
}
// 마지막 바위와 도착지점 사이의 거리를 확인합니다.
if (distance - prev < mid) { // 마지막 바위와 도착지점 사이의 거리가 mid보다 작으면
removed++; // 바위를 제거합니다.
}
// 제거한 바위의 개수가 n보다 작거나 같으면
if (removed <= n) {
answer = mid; // 결과를 갱신합니다.
left = mid + 1; // 최소 거리를 늘립니다.
} else { // 그렇지 않으면
right = mid - 1; // 최대 거리를 줄입니다.
}
}
return answer;
}
}
tmi : 이분 탐색이 아닌 다른 풀이로 접근해서 풀어봤는데 시간 초과가 발생했다. 문제의 본질을 이해하고 접근하는것도 중요하다고 느끼게 되었다.
📚 풀이 보완
코드 설명
- 정렬: Arrays.sort(rocks);를 통해 바위의 위치를 오름차순으로 정렬합니다.
- 이분 탐색: 최소 거리의 최솟값을 left, 최대값을 right로 설정하고, 이분 탐색을 시작합니다.
- 중간 값 계산: mid = (left + right) / 2로 현재 탐색 범위의 중간 값을 계산합니다.
- 그리디 검증:
- removed를 0으로 초기화하고, 이전 바위 위치 prev를 0으로 초기화합니다.
- 각 바위에 대해 현재 바위와 이전 바위 사이의 거리가 mid보다 작으면 바위를 제거합니다.
📍 Plus+
공간 복잡도
- 입력 데이터 저장 공간: distance (정수), rocks (정수 배열), n (정수)
- 추가 배열이나 데이터 구조: 정렬된 rocks 배열을 저장하기 위해 추가 메모리가 필요하지 않으며, 기존 배열을 정렬합니다.
따라서, 입력 데이터의 크기 n이 바위의 개수라고 할 때, 공간 복잡도는 O(n)입니다.
시간복잡도
- 정렬: rocks 배열을 정렬하는데 걸리는 시간. Java의 Arrays.sort() 메서드는 퀵소트 알고리즘을 사용하여 평균 시간 복잡도가 O(n log n)입니다.
- 이분 탐색: 가능한 최소 거리의 최댓값을 찾기 위해 이분 탐색을 수행합니다. 이분 탐색의 시간 복잡도는 O(log M)입니다. 여기서 M은 distance입니다.
- 검증 단계: 각 이분 탐색 단계에서 현재 중간 값이 최소 거리로 설정되었을 때, 이를 만족하도록 바위를 제거할 수 있는지 확인합니다. 이 단계는 바위의 개수 n에 비례하여 실행되므로 O(n)입니다.
요약
- 공간 복잡도 : O(n)
- 시간 복잡도 : O(n log n + n log M)
'Algorithm > 코딩테스트' 카테고리의 다른 글
[프로그래머스][JAVA] 49190. 방의 개수 (1) | 2024.06.16 |
---|---|
[리트코드][JAVA] 786. K-th-smallest-prime-fraction (K번째로 작은 소수 분수) (1) | 2024.06.11 |
[프로그래머스][JAVA] 42897. 도둑질 (0) | 2024.06.09 |
[프로그래머스][JAVA] 1843. 사칙연산 (0) | 2024.06.09 |
[프로그래머스][JAVA] 43105. 정수 삼각형 (0) | 2024.06.09 |