[백준] 2217번 : 로프

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

첫 시도

const fs = require("fs");
let [count,...rest] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const numData = {};
const result = [];
const deduplicatedArr = [...new Set(rest)]

rest.forEach((el) => {
    if(!numData[el]) {
        numData[el] = 1;
    } else {
        numData[el] += 1;
    }
})


deduplicatedArr.forEach((el) => {
    let data = 0;
    for( const [key,val] of Object.entries(numData)) {
        if(key >= el) {
            data += val * el
        }
    }
    result.push(data)
})

console.log(Math.max(...result));

사실 심한 경우 n^2 + n이 나오는 최악의 경우를 고려했다.
이게 답이 맞아보이긴 하지만 시간 초과가 떴다. 각 로프의 개수와 하중을 객체로 관리하여서, 순서를 알 수 없기 때문에 불필요하게 for문을 밑에서 한번 더 돌릴 수 밖에 없었다.

두번째 시도

const fs = require("fs");
let [count,...rest] = fs.readFileSync("/dev/stdin").toString().split("\n").map(Number);

rest.sort((a, b) => {
  return a - b;
});

let result = [];

rest.forEach((_, idx) => {
  if (idx == 0) {
    result.push(count * rest[0]);
  }
  if (!rest[idx + 1]) return;

  if (rest[idx] === rest[idx + 1]) return;

  result.push(rest[idx + 1] * (rest.length - (idx + 1)));
});

console.log(Math.max(...result));

나머지 값들을 sort한 후, for문을 돌면서 해당 인덱스와 인덱스 뒤의 값이 다를 때를 포착하여 해당 인덱스의 뒤의 값(+1)과 전체 개수 중 해당 인덱스까지 뺀 값을 곱해보았다. 이렇게 되면 중첩 for문도 지워서 최악의 경우를 면할 수 있다.

회고

• sort() 메서드에 대해서 무지했다. sort() 메서드는 유니코드 문자열을 따르기 때문에, 일반 숫자를 정렬하기 위해서는 정렬 함수를 정의해주어야 했다. 나는 그것도 모르고 생으로 sort를 호출했는데 값이 안나와 애먹었었다. 안에 sort 함수를 정의하는 방법과 흐름에 대해 이해할 필요가 있다.
• rest parameter는 너무너무 편하다. 애용해야겠다.
• 코테에서 n^2은 절대로 허용하지 말자...!