BOJ 2012 with js _ 등수 매기기 (sort)

2012 with Node.js _ 등수 매기기

문제

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (

A - B

)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

정답 코드

const fs = require("fs");
const stdin = ( process.platform === "linux"? fs.readFileSync("/dev/stdin").toString() :
    `` // 기본 입력값 설정 (백준 코딩테스트에서 비워놔도 무방하다.)
).split("\n");

const input = (() => {  //input()을 호출할 때마다 한줄씩 읽어온다.
  let line = 0;
  return () => stdin[line++];
})();

let count = +input();
let checks = Array.from({length : count}, v => false); // 원하는 등수로 할당할 수 있는지 검사한다.
const lefts = [];

for(let i = 0; i < count; i++ ){
  const valueIndex = +input() - 1; // 등수를 index로 치환
  if(checks[valueIndex] == false){
    checks[valueIndex] = true;
  }
  else {
    lefts.push(valueIndex); // 원하는 등수가 할당 되었으면 나머지로 분류한다
  }
}
lefts.sort((a,b) => a-b); //오름차순 정렬
checks = checks.map((v,i) => v == false ? i : -1).filter(v => v > -1).sort((a,b) => a-b);
let result = 0;
// 차이의 최소값을 구하므로 index끼리 계산하여도 무방
// 오름차순 정렬을 하였으므로 순서대로 계산하면 최소값이 도출됨
lefts.forEach((v,i) => result = result + Math.abs(v-checks[i]));
console.log(result); // 결과 값 출력

살펴보아야 할 점

두 값의 차이의 최소 값을 구하는 경우이므로 오름 차순 정렬하여 각 순서에 맞는 값의 차이를 더해주면 최소값의 합으로 결론이 나온다.

Sort 함수 이용

sort 문서

기본 sort() 함수는 ASCII 코드 값으로 비교하므로 sort((prev, cur) => prev - cur) 이렇게 계산하여야 정확히 정렬된다.

문제 링크

https://www.acmicpc.net/problem/2012