Algorithm/코딩테스트

[프로그래머스][JAVA] 42884. 단속카메라

ioh'sDeveloper 2024. 6. 9. 22:36
💡 문제
단속카메라(https://school.programmers.co.kr/learn/courses/30/lessons/42884)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

  • 그리디 알고리즘: 그리디 알고리즘은 각 단계에서 최적의 선택을 하는 알고리즘입니다. 현재의 선택이 지역적으로는 최적이지만, 전체적으로는 최적해를 보장하지 않을 수 있습니다. 따라서 그리디 알고리즘을 적용할 때에는 각 단계에서 최적의 선택을 하여 전체 해답을 찾아내는 과정을 이해하고 적용해야 합니다.
  • 정렬 알고리즘: 정렬 알고리즘은 주어진 데이터를 특정한 기준에 따라 정렬하는 알고리즘입니다. 이 문제에서는 차량의 경로를 진입 지점을 기준으로 오름차순으로 정렬해야 합니다. 대표적인 정렬 알고리즘으로는 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등이 있습니다.
  • 자료구조: 자료구조는 데이터를 효율적으로 저장하고 조작하기 위한 구조를 말합니다. 이 문제에서는 카메라를 설치하는 위치를 실시간으로 관리해야 하므로, 적절한 자료구조를 선택하고 사용해야 합니다. 변수, 배열, 스택, 큐 등 다양한 자료구조가 있으며, 문제의 요구사항에 따라 적절한 자료구조를 선택하여 사용해야 합니다.
  • 탐욕적인 선택 속성과 최적 부분 구조: 그리디 알고리즘을 적용하기 위해서는 문제가 탐욕적인 선택 속성과 최적 부분 구조를 만족해야 합니다. 탐욕적인 선택 속성은 각 단계에서의 최적 선택이 전체 해답에 대해 최적임을 보장해야 하며, 최적 부분 구조는 문제의 최적해가 부분 문제의 최적해를 포함하는 구조여야 합니다.
  • 문제 해석 능력: 문제 해석 능력은 주어진 문제의 요구사항을 정확하게 이해하고 해석하는 능력을 말합니다. 주어진 문제를 읽고 필요한 정보를 추출하며, 문제 해결을 위한 알고리즘을 설계하는 데 있어서 매우 중요합니다. 문제 해석 능력이 부족하면 잘못된 해결 방법을 선택하거나 문제를 제대로 해결하지 못할 수 있습니다.

🤓 문제 풀이

🔨 문제 설명

이 문제는 차량의 경로를 고려하여 고속도로에 최소한의 카메라를 설치하는 문제입니다. 각 차량이 반드시 한 번은 카메라를 만나도록 해야 하므로, 차량의 진출 지점을 기준으로 카메라를 설치하는 것이 효율적입니다.

고속도로를 이동하는 차량이 최소 한 번 단속 카메라를 만나도록 카메라를 설치하는 문제를 해결해야한다. 문제의 핵심은 각 차량의 진출 지점을 기준으로 정렬하고, 그리디하게 접근하여 최소한의 카메라를 설치하는 것입니다. 이는 차량의 경로가 겹치는 구간을 최대화하면서 카메라 설치 지점을 결정하는 문제입니다.

🔨 접근 방법

  1. 차량의 이동 경로는 진입 지점과 진출 지점으로 주어집니다.
  2. 진입 지점을 기준으로 오름차순으로 정렬합니다.
  3. 차량들이 고속도로를 이동하는 경로를 정렬하고, 카메라를 설치할 최적의 지점을 찾아야 합니다.
  4. 카메라를 설치할 때, 현재 카메라의 위치에서 가장 많은 차량을 만날 수 있는 지점을 선택합니다. 이 지점은 현재 카메라의 위치보다 다음 차량의 진입 지점이 큰 경우에 해당합니다.
  5. 차량의 진출 지점을 기준으로 정렬한 뒤, 순차적으로 차량이 겹치는 지점에 카메라를 설치합니다.
  6. 선택한 지점에 카메라를 설치하고, 해당 차량을 만났다고 가정하여 카메라를 설치한 다음 차량의 진출 지점 이전까지의 모든 차량을 제거합니다.
  7. 현재 설치된 카메라로 커버할 수 없는 차량이 나오면, 그 차량의 진출 지점에 새로운 카메라를 설치합니다.
  8. 위 과정을 반복하여 모든 차량을 단속할 때까지 카메라를 설치합니다.

🔨 문제 풀이 과정

  1. routes 배열을 진입 지점을 기준으로 오름차순으로 정렬합니다.
  2. 초기 카메라 위치를 -30001로 설정합니다. (최소값에서 시작)
  3. 각 차량의 경로를 순회하면서 카메라를 설치할 위치를 결정합니다.
  4. 만약 현재 차량의 진입 지점이 현재 카메라 위치보다 큰 경우, 새로운 카메라를 설치합니다. 그리고 현재 차량의 진출 지점 이전까지의 모든 차량을 단속했다고 가정하여 카메라를 설치한 다음 차량의 진출 지점으로 갱신합니다.
  5. 위 과정을 모든 차량에 대해 반복하면서 설치된 카메라의 수를 세고, 최종적으로 카메라의 수를 반환합니다.

🔨 그리드 선택

이 문제에서는 각 차량의 경로를 순회하면서 카메라를 설치하는 최적의 위치를 찾아야 합니다. 즉, 그리디한 방식으로 각 단계에서 최적의 선택을 해야 합니다.

그리디 알고리즘은 매 순간마다 가장 최적(또는 최선)인 선택을 하는 알고리즘입니다. 각 단계에서는 그 순간에 최적인 선택을 하며, 이 선택들을 모아서 문제의 최종 해결책을 찾아냅니다. 이때, 각 선택이 지역적으로는 최적이지만, 전체적으로는 최적해를 보장하지 않을 수 있습니다.

이러한 특성 때문에 그리디 알고리즘은 탐욕적인 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 만족해야 합니다.

  • 탐욕적인 선택 속성: 각 단계에서의 최적 선택이 전체 해답에 대해 최적임을 보장해야 합니다. 즉, 지금 당장의 선택이 전체 해답에 영향을 주지 않아야 합니다.
  • 최적 부분 구조: 문제의 최적해가 부분 문제의 최적해를 포함하는 구조여야 합니다. 즉, 전체 문제의 최적해가 부분 문제의 최적해를 이어붙여 구성되어야 합니다.

그리디 알고리즘은 전체적인 최적해를 구하기 위해 지역적으로 최적인 선택을 반복하는 과정을 수행합니다. 이 과정에서는 반드시 모든 선택지를 고려할 필요는 없습니다. 그저 각 단계에서 가장 최적인 선택을 하여 문제를 푸는 것이 그리디 알고리즘의 핵심입니다.

예를 들어, 거스름돈 문제에서는 지금 가장 큰 단위의 동전을 선택하는 것이 최적해를 보장합니다. 이러한 선택을 반복하면서 최종적으로는 거스름돈을 가장 적은 수의 동전으로 줄 수 있는 방법을 찾을 수 있습니다.

그리디 알고리즘은 간단하고 직관적인 방식으로 문제를 해결할 수 있으며, 대부분의 경우 효율적인 솔루션을 제공합니다. 그러나 모든 문제에 적용될 수 있는 것은 아니며, 최적 부분 구조와 탐욕적인 선택 속성을 만족하는 문제에만 적용할 수 있습니다.

🔨 구현코드

1) 탐욕법

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        // 차량 경로를 진출 지점 기준으로 오름차순 정렬
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        
        // 카메라 설치 횟수
        int answer = 0;
        // 마지막으로 설치한 카메라 위치
        int cameraPosition = Integer.MIN_VALUE;

        for (int[] route : routes) {
            // 현재 차량의 진입 지점이 마지막으로 설치한 카메라 위치보다 뒤에 있는 경우
            if (cameraPosition < route[0]) {
                // 새로운 카메라 설치
                cameraPosition = route[1];
                // 카메라 설치 횟수 증가
                answer++;
            }
        }
        
        return answer;
    }
}

 

2)다른 방식

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        // routes 배열을 진입 지점을 기준으로 오름차순으로 정렬
        Arrays.sort(routes, (a, b) -> Integer.compare(a[0], b[0]));
        
        int answer = 0; // 카메라의 수
        int camera = -30001; // 초기 카메라 위치 ,  초기 카메라 위치를 설정합니다. 최소값에서 시작하므로 -30001로 초기화합니다.
        
        for (int i = 0; i < routes.length; i++) {
            int entry = routes[i][0]; // 현재 차량의 진입 지점
            int exit = routes[i][1]; // 현재 차량의 진출 지점
            
            // 현재 차량의 진입 지점이 현재 카메라 위치보다 크면
            // 새로운 카메라를 설치하고 카메라를 설치한 다음 차량의 진출 지점으로 갱신
            if (entry > camera) {
                answer++; // 카메라 설치
                camera = exit; // 카메라 위치 갱신, 현재 차량을 만났다고 가정하여 카메라를 설치한 다음 차량의 진출 지점까지 제거합니다. 현재 카메라 위치를 현재 차량의 진출 지점과 비교하여 작은 값으로 갱신합니다.
            }
            
            // 현재 차량을 만났다고 가정하여 카메라를 설치한 다음 차량의 진출 지점까지 제거
            camera = Math.min(camera, exit);
        }
        
        return answer;
    }
}

📚 풀이 보완

코드 설명

  • 정렬:
    • Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1])); : 차량의 경로를 진출 지점을 기준으로 오름차순 정렬합니다.
  • 카메라 설치 로직:
    • cameraPosition : 마지막으로 카메라를 설치한 위치를 저장합니다.
    • cameraPosition < route[0] : 현재 차량의 진입 지점이 마지막으로 설치한 카메라 위치보다 뒤에 있는 경우를 확인합니다.
    • 새로운 카메라를 현재 차량의 진출 지점에 설치하고, 카메라 설치 횟수를 증가시킵니다

📍 Plus+

공간 복잡도

알고리즘이 실행되는 동안 사용되는 메모리의 양을 나타냅니다. 즉, 알고리즘이 동작하는 데 필요한 추가적인 메모리 공간의 크기입니다. 공간 복잡도는 보통 알고리즘의 입력 크기에 따라 결정되며, 일반적으로 고정된 공간(상수 공간)을 사용하는 알고리즘은 O(1)의 공간 복잡도를 가지고, 입력 크기에 비례하여 메모리를 사용하는 알고리즘은 O(n)의 공간 복잡도를 가집니다.

 

시간복잡도

알고리즘이 실행되는 데 걸리는 시간의 양을 나타냅니다. 일반적으로 알고리즘의 입력 크기에 따라서 시간이 얼마나 걸리는지를 나타내며, 주로 Big O 표기법을 사용하여 표현됩니다. 시간 복잡도를 표기할 때는 주로 최악 경우를 고려하며, 최선, 평균 경우의 시간 복잡도를 고려하기도 합니다.

 

요약

  • 공간 복잡도: 알고리즘이 실행되는 동안 사용되는 메모리의 양을 나타냅니다. 주로 입력 크기에 따라 결정되며, 일반적으로 Big O 표기법을 사용하여 표현됩니다.
  • 시간 복잡도: 알고리즘이 실행되는 데 걸리는 시간의 양을 나타냅니다. 주로 입력 크기에 따라 결정되며, 일반적으로 Big O 표기법을 사용하여 표현됩니다.

 

수학적접근 방식

수학적 접근

수학적으로 이 문제를 접근할 때는 차량의 이동 경로를 일종의 "구간"으로 생각할 수 있습니다. 각 차량의 경로는 시작 지점과 끝 지점으로 이루어진 구간이며, 모든 구간을 최소한 한 번은 겹치도록 카메라를 설치하는 문제입니다.

수학적 접근 방법

  1. 정렬: 차량의 이동 경로를 진출 지점 기준으로 오름차순으로 정렬합니다. 이는 가장 빨리 고속도로를 나가는 차량부터 처리하여, 해당 차량의 진출 지점에 카메라를 설치하는 것이 최적임을 이용합니다.
  2. 탐욕법 (그리디 알고리즘): 각 차량의 경로를 순차적으로 확인하면서, 현재 설치된 카메라의 위치가 다음 차량의 진입 지점보다 앞에 있는지 확인합니다. 만약 그렇지 않다면, 새로운 카메라를 현재 차량의 진출 지점에 설치합니다.

이 접근 방법의 수학적 근거는 다음과 같습니다:

  • 차량의 진출 지점을 기준으로 정렬하면, 현재 차량의 진출 지점에 카메라를 설치하는 것이 이후 차량들의 경로를 최대한 많이 커버할 수 있습니다.
  • 새로운 카메라를 설치하는 시점은 항상 이전 카메라로 커버할 수 없는 새로운 구간이 시작될 때입니다.

수학적 증명

  • 모든 차량의 경로를 진출 지점 기준으로 정렬하면, i번째 차량의 진출 지점 $Ei$는 항상
  • i−1번째 차량의 진출 지점 Ei−1보다 크거나 같습니다. 즉, E1≤E2≤...≤En입니다.$
  • 첫 번째 차량의 진출 지점에 카메라를 설치하면, 이후 차량들이 이 카메라에 의해 커버될 수 있는지를 확인합니다.
  • 만약 현재 설치된 카메라가 i번째 차량의 진입 지점 $Si$보다 앞에 있으면, $i$번째 차량은 이미 설치된 카메라에 의해 커버됩니다.
  • 그렇지 않으면 새로운 카메라를 $i$번째 차량의 진출 지점에 설치합니다.
import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        // 정렬: 차량 경로를 진출 지점 기준으로 오름차순 정렬 이는 그리디 알고리즘의 핵심 부분으로, 가장 빨리 고속도로를 나가는 차량부터 처리
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        
        int answer = 0;
        // 초기화 : 마지막으로 카메라가 설치된 위치를 저장합니다. 초기값은 최소값으로 설정하여 첫 번째 차량에 대해 무조건 카메라를 설치하도록 합니다.
        int cameraPosition = Integer.MIN_VALUE;
        
        // 탐색: 모든 차량의 경로를 순회하면서 현재 차량이 기존 카메라로 커버되지 않는 경우 새로운 카메라를 설치합니다.
        for (int[] route : routes) {
            // 현재 차량의 진입 지점이 마지막 카메라 위치보다 크다면 새로운 카메라 설치 필요
            if (cameraPosition < route[0]) {
                // 새로운 카메라를 현재 차량의 진출 지점에 설치하고, 카메라 위치를 업데이트
                cameraPosition = route[1];
                // 카메라 개수 증가 :새로운 카메라를 설치했으므로 카메라의 개수를 증가시킵
                answer++;
            }
        }
        
        return answer;
    }
}

 

'Algorithm > 코딩테스트' 카테고리의 다른 글

[프로그래머스][JAVA] 43105. 정수 삼각형  (0) 2024.06.09
[프로그래머스][JAVA] 42895. N으로 표현  (1) 2024.06.09
[프로그래머스][JAVA] 42861. 섬연결하기  (1) 2024.06.09
[프로그래머스][JAVA] 43162. 네트워크  (1) 2024.06.09
[프로그래머스][JAVA] 43163. 단어변환  (1) 2024.06.09

'Algorithm/코딩테스트'의 다른글

  • 현재글[프로그래머스][JAVA] 42884. 단속카메라

관련글

티스토리툴바