[백준] JavaScript - 센서 (2212)

개요

문제 이름: 센서 (2212)
문제 링크: https://www.acmicpc.net/problem/2212
플랫폼: 백준
알고리즘 분류: 그리디 알고리즘, 정렬
소요 시간: 1시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 그리디 알고리즘을 사용하여 최소한의 수신 영역으로 모든 센서를 커버하는 문제입니다.

 

문제를 요약하면 다음과 같습니다.

• N개의 센서가 일직선 상에 위치하고 있습니다.
• 최대 K개의 집중국을 설치하여 모든 센서를 커버해야 합니다.
• 각 집중국은 일정 수신 가능 영역을 가지며, 이 영역들의 길이의 합을 최소화해야 합니다.

문제 접근 방법은 다음과 같습니다.

1. 먼저 센서의 개수 N이 집중국의 개수 K보다 작거나 같은 경우를 처리합니다. 이 경우에는 각 센서에 하나씩 집중국을 배치하면 되므로 수신 영역의 합은 0이 됩니다.
2. N > K인 경우, 센서들을 오름차순으로 정렬한 후 인접한 센서 사이의 거리 차이를 계산합니다. 이 거리 차이들이 집중국이 커버해야 할 간격을 나타냅니다.
3. 거리 차이를 내림차순으로 정렬합니다. 이는 가장 큰 간격부터 제거하기 위함입니다.
4. K-1개의 가장 큰 간격을 제거합니다. 이렇게 하면 K개의 집중국으로 분할된 영역이 만들어집니다.
5. 나머지 간격들의 합을 계산하여 최종 결과를 출력합니다. 이것이 최소 수신 영역의 길이가 됩니다.

즉, 그리디 알고리즘으로 가장 큰 간격부터 제거해 나가면서 K개의 영역으로 분할하는 것이 이 문제의 핵심이라고 할 수 있겠습니다. 이를 통해 최소한의 수신 영역으로 모든 센서를 커버할 수 있습니다.

 

시도

1차 시도  (성공)

// 파일 시스템 모듈을 불러오고, 공백과 줄바꿈을 기준으로 분리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 개수 N & K을 정수로 변환하여 저장
const N = parseInt(input[0]);
const K = parseInt(input[1]);

// 센서의 위치를 공백으로 구분하여 배열로 생성
// 각 문자열을 숫자로 변환한 후, 오름차순으로 정렬
const sensors = input[2].split(' ').map(Number).sort((a, b) => a - b);

// 센서의 개수가 집중국의 개수보다 작거나 같은 경우를 처리
if (N <= K) {
    // 이 경우, 각 센서에 하나씩 집중국을 배치할 수 있으므로 수신 영역의 합은 0
    console.log(0);
} else {
    // 인접한 센서 사이의 거리 차이를 계산하여 배열에 저장
    // 이 차이들이 나중에 집중국이 커버해야 하는 간격을 나타냄
    const diff = [];
    for (let i = 1; i < sensors.length; i++) {
        // 현재 센서와 이전 센서 사이의 거리 차이를 계산
        diff.push(sensors[i] - sensors[i - 1]);
    }
    
    // 계산된 거리 차이를 내림차순으로 정렬
    // 가장 큰 차이부터 정렬되므로, 나중에 큰 차이를 제외하기 쉬워짐
    diff.sort((a, b) => b - a);
    
    // K개의 집중국으로 센서를 모두 커버하려면, 센서들을 K개의 그룹으로 나누어야 함
    // 이는 센서 사이의 (K-1)개의 연결을 끊는 것과 같음
    // 가장 큰 (K-1)개의 차이를 제거하면, K개의 연속된 센서 그룹이 생성됨
    // 각 그룹은 하나의 집중국이 담당하게 됨
    
    // 결과값을 저장할 변수를 초기화
    let result = 0;
    
    // K-1개의 가장 큰 차이를 제외한 나머지 차이들의 합을 계산
    // 이 합이 최소 수신 영역의 길이
    for (let i = K - 1; i < diff.length; i++) {
        result += diff[i];
    }
    
    // 최종 결과를 출력
    console.log(result);
}

위의 코드는 그리디 알고리즘을 사용하여 문제를 해결했습니다.

1. 파일 시스템 모듈 fs를 사용하여 표준 입력으로부터 데이터를 읽어옵니다.
2. 첫 번째 줄에서 센서의 개수 N을 parseInt()로 정수로 변환하여 저장합니다.
3. 두 번째 줄에서 집중국의 개수 K를 parseInt()로 정수로 변환하여 저장합니다.
4. 세 번째 줄에서 센서의 위치를 공백으로 구분하여 split(' ')로 배열로 만들고, map(Number)로 각 문자열을 숫자로 변환한 후, sort((a, b) => a - b)로 오름차순으로 정렬합니다.
5. 센서의 개수 N이 집중국의 개수 K보다 작거나 같은 경우를 먼저 처리합니다. 이 경우에는 각 센서에 하나씩 집중국을 배치할 수 있으므로 수신 영역의 합은 0이 됩니다. 따라서 바로 0을 출력하고 프로그램을 종료합니다.
6. N > K인 경우에는 다음 단계를 진행합니다.
7. 인접한 센서 사이의 거리 차이를 계산하여 diff 배열에 저장합니다. 이는 for 반복문을 사용하여 현재 센서와 이전 센서의 위치 차이를 diff.push()로 배열에 추가합니다. 이렇게 계산된 거리 차이들이 나중에 집중국이 커버해야 할 간격을 나타냅니다.
8. 계산된 거리 차이를 sort((a, b) => b - a)로 내림차순으로 정렬합니다. 이는 가장 큰 차이부터 정렬되므로, 나중에 큰 차이를 제외하기 쉽게 만듭니다.
9. 그리디 알고리즘의 핵심 부분입니다. K개의 집중국으로 센서를 모두 커버하려면, 센서들을 K개의 그룹으로 나누어야 합니다. 이는 센서 사이의 (K-1)개의 연결을 끊는 것과 같습니다. 가장 큰 (K-1)개의 차이를 제거하면, K개의 연속된 센서 그룹이 생성되고, 각 그룹은 하나의 집중국이 담당하게 됩니다.
10. 결과값을 저장할 변수 result를 초기화합니다.
11. for 반복문을 사용하여 K-1개의 가장 큰 차이를 제외한 나머지 차이들의 합을 계산합니다. 이 합이 최소 수신 영역의 길이가 됩니다.
12. 마지막으로 result에 저장된 값을 console.log()로 출력합니다.

 

시간복잡도와 공간복잡도

• 시간복잡도: O(N log N)
  • 센서의 위치를 정렬하는 데 O(N log N)의 시간이 소요됩니다.
  • 인접한 센서 사이의 거리 차이를 계산하고 정렬하는 데 O(N log N)의 시간이 소요됩니다.
  • 따라서 전체 시간복잡도는 O(N log N)입니다.
• 공간복잡도: O(N)
  • 센서의 위치를 저장하는 배열 sensors의 크기가 O(N)입니다.
  • 인접한 센서 사이의 거리 차이를 저장하는 배열 diff의 크기도 O(N)입니다.
  • 따라서 공간복잡도는 O(N)입니다.

 

사용된 주요 메서드

• String.prototype.trim(): 문자열 양 끝의 공백을 제거하는 메서드입니다.
• String.prototype.split(separator[, limit]): 문자열을 지정한 구분자를 기준으로 분할하여 배열로 반환하는 메서드입니다. 구분자와 선택적으로 분할할 최대 개수를 인자로 받습니다.
• Array.prototype.map(callback(currentValue[, index[, array]])[, thisArg]): 배열의 모든 요소에 대해 제공된 함수를 호출한 결과를 모아 새로운 배열을 반환하는 메서드입니다.
• Array.prototype.sort(compareFn): 배열의 요소를 정렬하는 메서드입니다. 선택적으로 정렬 순서를 정의하는 비교 함수를 인자로 받을 수 있습니다.
• Array.prototype.push(...items): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환하는 메서드입니다.
• parseInt(string, radix): 문자열을 파싱하여 특정 진수의 정수를 반환하는 함수입니다. 문자열과 선택적으로 진수를 나타내는 기수(radix)를 인자로 받습니다.
• console.log(...data): 콘솔에 메시지를 출력하는 메서드입니다. 하나 이상의 값을 인자로 받아 콘솔에 출력합니다.