백준 3655 먼저 가세요

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

문제

문제를 읽는데 제대로 이해를 하지 못해 문제를 읽는 시간이 길었던 문제였다. 이 스키장에서 친구가 아직 도착하지 않았다면 줄을 양보하면서 양보받은 그룹이 아낀 시간들을 계산해야 한다.

친구가 아직 리프트에 도착하지 않았다면 최대한 기다려야 하기 때문에 각 그룹이 양보 전 기다려야 하는 인덱스를 모두 담은 뒤, 기다려야 하는 인덱스가 적은 순서대로 문자열을 정렬한다. 인덱스가 적은 순서대로 정렬하면 먼저 갈 수 있는 사람은 먼저 앞의 그룹이 아직 다 오지 않은 상태라는 소리이기 때문에 양보받아 갈 수 있다. 이후에 정렬한 문자열을 기반으로 다시금 양보 후 기다려야 하는 인덱스를 모두 담고, 양보 전과 비교하여 얼마나 더 절약했는지를 계산하면 된다.

결국 마지막에 각 그룹이 아낀 시간을 계산하면 되므로, 앞에서 친구를 기다리던 사람들과 뒤에서 빠르게 양보받아 온 사람 모두 시간을 아끼는 셈이 된다. 따라서 이전 위치에서 가졌던 마지막 사람의 인덱스 - 현재 위치에서 가지는 마지막 사람의 인덱스 * 사람 수 * 5 를 계산하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const q = require("fs").readFileSync(INPUT_FILE).toString().trim().split("\n");
 
for (let i = 1; i < q.length; i += 2) {
  const n = +q[i];
  const people = q[i + 1].split("");
  const last = {};
  people.forEach((person, idx) => {
    last[person] = idx;
  });
  people.sort((a, b) => last[a] - last[b]);
  const afterSort = {};
  people.forEach((person, idx) => {
    afterSort[person] = idx;
  });
  let cnt = {};
  people.forEach((person) => {
    cnt[person] = (cnt[person] || 0) + 1;
  });
 
  let acc = 0;
  for (const [key, val] of Object.entries(cnt)) {
    acc += (last[key] - afterSort[key]) * val * 5;
  }
  console.log(acc);
}

문제 이해가 어려워 결국 도움을 받아 찝찝한 마음이다..흑