문제

크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다.

한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 합하여 계산한다. 점수는 자격을 갖춘 팀의 주자들에게만 주어지며, 결승점을 통과한 순서대로 점수를 받는다. 이 점수를 더하여 가장 낮은 점수를 얻는 팀이 우승을 하게 된다. 여섯 명의 주자가 참가하지 못한 팀은 점수 계산에서 제외된다. 동점의 경우에는 다섯 번째 주자가 가장 빨리 들어온 팀이 우승하게 된다.

예를 들어, 다음의 표를 살펴보자.

팀 B 와 D 는 선수의 수가 여섯이 아니므로, 점수를 받을 수 없다. 팀 A 의 점수는 18 (1+4+6+7)이고, 팀 C 의 점수는 18 (2+3+5+8)이다. 이 경우 두 팀의 점수가 같으므로 다섯 번째로 결승점을 통과한 선수를 고려한다, A 팀의 다섯 번째 선수의 점수가 C 팀의 다섯 번째 선수의 점수보다 적으므로 A 팀이 우승팀이 된다.

모든 선수들의 등수가 주어질 때, 우승팀을 구하는 프로그램을 작성하라. 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 여섯 명 보다 많은 선수가 참가하는 팀은 없고, 적어도 한 팀은 참가 선수가 여섯이며, 모든 선수는 끝까지 완주를 한다고 가정한다.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (6 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 팀 번호를 나타내는 N 개의 정수 t1, t2, …, tN 이 공백을 사이에 두고 주어진다. 각 팀은 1 과 M(1 ≤ M ≤ 200)사이의 정수로 표현된다.

출력

출력은 표준출력을 사용한다. 하나의 테스트 케이스에 대한 우승팀의 번호를 한 줄에 출력한다.

예제 입력

2
15
1 2 3 3 1 3 2 4 1 1 3 1 3 3 1
18
1 2 3 1 2 3 1 2 3 3 3 3 2 2 2 1 1 1

예제 출력

1
3

내가 했던 풀이 방법

1. team이라는 Map을 선언해 players들을 팀별로 묶어준다. 이때, 팀번호와 등수를 모두 알 수 있도록 "팀번호_등수"의 문자열을 value로 넣어준다.
2. validTeam 배열을 만들고 team의 정원이 6명이 아닌 팀을 제거해준다. 6명인 팀은 validTeam 배열에 value 값을 push해준다. 이렇게 되면 정원을 충족하지 않은 참가자를 제외한 모든 유효한 선수들의 팀번호와 등수만이 validTeam에 담기게 된다.
3. validTeam을 등수 오름차순으로 정렬해준다.
4. score을 teamCount 크기의 배열로 선언해주고 모든 값을 [0, 0, Infinity, 0]로 초기화해준다. [상위 4팀의 점수, 현재까지 계산된 팀원 수, 팀내 5등의 등수, 팀번호]가 들어가게 될 것이다.
5. 제거된 선수를 제외하고 등수를 다시 계산해주어야 하므로 등수에 사용될 변수 point를 1로 초기화해준다.
6. validTeam을 순차적으로 돌면서, 현재 팀의 계산된 팀원 수가 4를 넘어가지 않았다면, 상위 4팀의 점수에 point를 더해주고, 계산된 팀원 수를 1 증가시켜준다. 만약 넘어갔다면, 팀내 5등의 등수를 넣어준다. 팀내 5등의 등수는 초기에 Infinity로 되어 있고 최솟값으로 넣어주기 때문에, 6번째 선수의 값이 들어와도 5등의 등수가 그대로 남게 된다. 이렇게 하지 않으려면, 해당 값은 먼저 들어오는 값이 무조건 5등의 등수이므로 해당 값이 Infinity가 아닐 때만 덮어쓰기 해주면 된다. 항상 팀번호는 teamNum을 넣어주면 된다. 계속 덮어쓰여지기 때문에 한 번만 쓰게 하고 싶다면 0이 아닐 때 넣어주면 된다. 매 반복마다 point를 증가시켜주면서 모든 선수들의 새로운 등수를 계산해준다.
7. 계산된 score를 상위 4팀의 점수에 따라 오름차순으로 정렬해준다. 만약 같은 값이 있다면 팀내 5등의 등수를 기준으로 오름차순 정렬해준다.
8. 팀원을 충족하지 않은 팀원이 있다면 무조건 score의 첫번째 값은 [0, 0, Infinity, 0]이 될 것이다. 이를 삭제된 팀원 수를 알고있다면, 따로 정리해줄 필요는 없지만, score에 조건에 부합한 팀원들만 남겨두기 위해 filter를 사용해서 [0, 0, Infinity, 0] 값을 모두 제거해주었다.
9. filteredScore의 가장 첫번째 요소의 팀번호를 answer에 더해준다.
10. 1~9번을 testcase만큼 반복해준다.

코드

const fs = require('fs');
let [T, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let index = 0;
let answer = '';
for (let i = 0; i < Number(T); i++) {
  let N = Number(input[index++]);
  let players = input[index++].trim().split(' ').map(Number);

  let team = new Map();
  for (let j = 0; j < N; j++) {
    if (team.has(players[j])) {
      team.set(players[j], [...team.get(players[j]), `${players[j]}_${j}`]);
    } else {
      team.set(players[j], [`${players[j]}_${j}`]);
    }
  }

  let validTeam = [];
  let teamCount = 0;
  for (let member of team) {
    if (member[1].length < 6) team.delete(member[0]);
    else {
      validTeam.push(...member[1]);
    }
    teamCount++;
  }

  validTeam.sort((a, b) => {
    let rankA = a.split('_').map(Number)[1];
    let rankB = b.split('_').map(Number)[1];

    if (rankA < rankB) return -1;
    else return 1;
  });

  let score = Array.from({ length: teamCount }, () => [0, 0, Infinity, 0]);
  let point = 1;
  for (let j = 0; j < validTeam.length; j++) {
    let [teamNum, rank] = validTeam[j].split('_').map(Number);
    if (score[teamNum - 1][1] < 4) {
      score[teamNum - 1][0] += point;
      score[teamNum - 1][1]++;
    } else {
      score[teamNum - 1][2] = Math.min(score[teamNum - 1][2], j);
    }
    score[teamNum - 1][3] = teamNum;
    point++;
  }

  score.sort((a, b) => {
    if (a[0] < b[0]) return -1;
    else if (a[0] > b[0]) return 1;
    else {
      if (a[2] < b[2]) return -1;
      else return 1;
    }
  });

  let filteredScore = score.filter((item) => !item.every((val, index) => val === [0, 0, Infinity, 0][index]));

  answer += filteredScore[0][3] + '\n';
}

console.log(answer.trim());

회고

정말 구현 그자체.... 코드가 오랜만에 복잡했고... 설명하기도 난해하긴한데 문제를 딱 보자마자 느낀 건 map을 이용해서 조건에 부합하지 않은 팀을 제거해주자였다. 제거를 한 뒤에 등수를 매기는 부분이 정말 귀찮고 까다로웠지만 해당 부분을 하지 않으면 팀 점수를 정확하게 구할 수가 없어서 map을 이용해 팀을 제거하고 배열 정렬을 이용해서 조건에 부합한 팀원들의 점수를 계산해주었다. 그냥 총점으로만 따졌다면 쉬웠을텐데 상위 4팀만 구해야하고 5등의 등수도 알고있어야 해서 진짜 구현할 게 많았던 문제...