[BOJ][⚪1][백준#16564] 히오스 프로게이머

문제 출처

BAEKJOON Online Judge #16564

문제

성권이는 Heroes of the Storm 프로게이머 지망생이다. 이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다. 팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가? 예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.

입력

첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, … , Xn 으로 주어진다. (1 ≤ Xi ≤ 1,000,000,000)

출력

가능한 최대 팀 목표레벨 T를 출력한다.

예제

입력

3 10
10
20
15

출력

17

My Sol

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split("\n")
  .map((a) => a.trim());

let [N, K] = input[0].split(" ").map(Number);
const obj = {};
for (let i = 0; i < N; i++) {
  const n = input[i + 1];
  obj[n] = obj[n] ? obj[n] + 1 : 1;
}

const levels = Object.keys(obj)
  .map(Number)
  .sort((a, b) => a - b);

const ll = levels.length;
let sames = obj[levels[0]];
let ret = +levels[0];
let i = 0;

while (K > 0 && i < ll && sames * (levels[i + 1] - levels[i]) <= K) {
  K -= sames * (levels[i + 1] - levels[i]);
  sames += obj[levels[i + 1]];
  ret = levels[i + 1];
  i++;
}

ret += Math.floor(K / sames);
console.log(ret);

1. 객체에 레벨들의 개수를 등록한다.
2. 레벨들을 숫자로 변환하여 오름차순 정렬한다.
3. 레벨들마다의 개수를 누적하며 다음 레벨까지 한 번에 모두 올릴 수 있는지 확인한다.
4. 더이상 한 번에 레벨업을 할 수 없다면 반복을 마친다.
5. 남은 K를 누적된 레벨의 개수로 나눈 몫을 ret에 더한다.
6. 이를 출력한다.

결과

맞았습니다!!