[프로그래머스][JAVA] 43236. 징검다리

💡 문제
징검다리(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+

공간 복잡도

1. 입력 데이터 저장 공간: distance (정수), rocks (정수 배열), n (정수)
2. 추가 배열이나 데이터 구조: 정렬된 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)