[백준] JavaScript - 저울 (2437)

개요

문제 이름: 저울 (2437)
문제 링크: https://www.acmicpc.net/problem/2437
플랫폼: 백준
알고리즘 분류: 정렬
소요 시간: 30분

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 그리디 알고리즘을 사용하여 주어진 저울추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제입니다.

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

• N개의 저울추의 무게가 주어집니다.
• 이 저울추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구해야 합니다.

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

1. 입력으로 저울추의 개수 N과 각 저울추의 무게가 주어집니다.
2. 저울추의 무게를 오름차순으로 정렬합니다.
3. 정렬된 저울추를 순서대로 확인하면서, 현재까지 만들 수 있는 연속된 무게의 최댓값을 갱신합니다.
   1. 현재까지 만들 수 있는 무게보다 다음 저울추의 무게가 2 이상 크면, 연속성이 깨지므로 측정할 수 없는 최소 무게를 찾습니다.
   2. 그렇지 않으면, 현재 저울추를 사용하여 만들 수 있는 최대 무게를 갱신합니다.
4. 최종적으로 만들 수 없는 최소 무게는 현재까지 만들 수 있는 무게에 1을 더한 값입니다.

예를 들어, 저울추의 무게가 [1, 1, 2, 3, 6, 7, 30]인 경우를 생각해보면 다음과 같다고 할 수 있습니다.

1. 저울추를 오름차순으로 정렬합니다. [1, 1, 2, 3, 6, 7, 30]
2. 첫 번째 저울추 1을 사용하면, 1까지의 무게를 측정할 수 있습니다.
3. 두 번째 저울추 1을 사용하면, 1과 1+1=2까지의 무게를 측정할 수 있습니다.
4. 세 번째 저울추 2를 사용하면, 1, 2, 1+2=3, 1+1+2=4까지의 무게를 측정할 수 있습니다.
5. 네 번째 저울추 3을 사용하면, 1, 2, 3, 4, 1+3=4, 2+3=5, 1+2+3=6, 1+1+2+3=7까지의 무게를 측정할 수 있습니다.
6. 다섯 번째 저울추 6을 사용하면, 이전까지 만들 수 있는 무게에 6을 더해 13까지의 무게를 측정할 수 있습니다.
7. 여섯 번째 저울추 7을 사용하면, 이전까지 만들 수 있는 무게에 7을 더해 20까지의 무게를 측정할 수 있습니다.
8. 일곱 번째 저울추 30은 현재까지 만들 수 있는 최대 무게 20보다 크므로, 21이 측정할 수 없는 최소 무게가 됩니다.

즉, 저울추를 하나씩 추가하면서 만들 수 있는 무게의 범위를 늘려가다가, 다음 저울추의 무게가 이전까지 만들 수 있는 최대 무게 + 1보다 크게 되는 순간 그 값이 측정할 수 없는 최소 무게가 됩니다.

 

결국 그리디 알고리즘을 적용하여 저울추를 오름차순으로 정렬하고, 각 저울추를 순서대로 확인하면서 연속된 무게를 만들 수 있는지 판단하는 것이 핵심입니다.

 

시도

1차 시도  (성공)

// 파일 시스템 모듈을 불러오고, 입력을 받습니다.
// 문자열로 변환한 후 양쪽 공백을 제거하고 줄바꿈(\n)으로 분리합니다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 첫 번째 줄에서 저울추의 개수 N을 가져와 정수로 변환합니다.
const N = parseInt(input[0]);

// 두 번째 줄에서 저울추의 무게들을 가져와 공백으로 분리하고, 각 문자열을 숫자로 변환한 후 오름차순으로 정렬합니다.
const weights = input[1].split(' ').map(Number).sort((a, b) => a - b);

// 현재까지 만들 수 있는 연속된 무게의 최댓값을 저장하는 변수입니다.
// 초기값은 0으로, 아직 아무 추도 사용하지 않았음을 의미합니다.
let possibleSum = 0;

// 정렬된 모든 추를 순서대로 확인합니다.
for (let i = 0; i < N; i++) {
    // 현재 추의 무게가 possibleSum + 1보다 크면 연속성이 깨지므로 반복문을 종료합니다.
    if (weights[i] > possibleSum + 1) {
        break;
    }
    
    // 현재 추를 사용하여 만들 수 있는 최대 무게를 갱신합니다.
    possibleSum += weights[i];
}

// 최종적으로 만들 수 없는 최소 무게는 possibleSum + 1입니다.
console.log(possibleSum + 1);

위의 코드는 그리디 알고리즘을 사용하여 문제를 해결한 것입니다. 코드의 주요 내용을 설명하면 다음과 같습니다.

1. 파일 시스템 모듈 fs를 사용하여 표준 입력으로부터 데이터를 읽어옵니다. 입력 데이터는 줄바꿈으로 구분되어 있으므로 split('\n')으로 분할합니다.
2. 첫 번째 줄에서 저울추의 개수 N을 분리하여 parseInt를 사용해 정수로 변환합니다.
3. 두 번째 줄에서 저울추의 무게들을 분리하고, map(Number)를 사용해 각 문자열을 숫자로 변환한 후 sort((a, b) => a - b)를 사용해 오름차순으로 정렬합니다.
4. 현재까지 만들 수 있는 연속된 무게의 최댓값을 저장할 변수 possibleSum을 0으로 초기화합니다. 이는 아직 아무 추도 사용하지 않았음을 의미합니다.
5. 정렬된 모든 추를 순서대로 확인하면서, 현재까지 만들 수 있는 무게보다 다음 추의 무게가 2 이상 크면 연속성이 깨지므로 만들 수 없는 최소 무게를 찾습니다.
   1. 만약 weights[i] > possibleSum + 1이면, 즉 현재 추의 무게가 지금까지 만들 수 있는 무게의 다음 수보다 크다면, 그 사이의 숫자는 만들 수 없으므로 루프를 종료합니다.
6. 그렇지 않다면, 현재 추를 사용하여 만들 수 있는 최대 무게를 갱신합니다.
   1. 이 시점에서 1부터 possibleSum까지의 모든 무게를 만들 수 있다고 가정했을 때, 새로운 추 weights[i]를 추가하면 weights[i]부터 possibleSum + weights[i]까지의 새로운 무게도 만들 수 있게 됩니다.
7. 최종적으로 만들 수 없는 최소 무게는 possibleSum + 1입니다. 이는 1부터 possibleSum까지는 모두 만들 수 있지만, 그 다음 숫자는 만들 수 없다는 의미입니다.

시간복잡도와 공간복잡도

• 시간복잡도: O(N log N)
  • 저울추의 무게를 정렬하는 데 O(N log N)의 시간이 소요됩니다.
  • 정렬된 저울추를 순서대로 확인하는 데 O(N)의 시간이 소요됩니다.
  • 따라서 전체 시간복잡도는 O(N log N)입니다.
• 공간복잡도: O(N)
  • 저울추의 무게를 저장하는 배열 weights의 크기가 O(N)입니다.
  • 따라서 공간복잡도는 O(N)입니다.

사용된 주요 메서드

• String.prototype.trim(): 문자열 양 끝의 공백을 제거하는 메서드입니다.
• String.prototype.split(separator[, limit]): 문자열을 지정한 구분자를 기준으로 분할하여 배열로 반환하는 메서드입니다. 구분자와 선택적으로 분할할 최대 개수를 인자로 받습니다.
• Array.prototype.map(callback(currentValue[, index[, array]])[, thisArg]): 배열의 모든 요소에 대해 제공된 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• Array.prototype.sort(compareFn): 배열의 요소를 정렬하고 정렬된 배열을 반환합니다. 선택적으로 정렬 순서를 정의하는 비교 함수를 인자로 받습니다. 비교 함수는 두 인자를 받아 그 차이를 반환해야 합니다.
• parseInt(string, radix): 문자열을 파싱하여 정수로 반환합니다. 문자열과 선택적으로 기수(radix)를 인자로 받습니다.