[백준] 8979_올림픽 (Javascript)

잭슨·2024년 3월 3일

구현 백준 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

22/130

문제

BOJ8979_올림픽

코드(20점)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const nations = input.slice(1).map((e) => e.split(' ').map(Number));
let dup = 1;

nations.sort((a, b) => {
    // 금메달 개수 비교
    if (a[1] > b[1]) return -1;
    else if (a[1] === b[1]) {
        // 은메달 개수 비교
        if (a[2] > b[2]) return -1;
        else if (a[2] === b[2]) {
            // 동메달 개수 비교
            if (a[3] > b[3]) return -1;
            else if (a[3] === b[3]) return 0;
            else return 1;
        } else return 1;
    } else return 1;
});

nations[0][4] = 1;
for (let i = 1; i < N; i++) {
    if (nations[i - 1][1] === nations[i][1] && nations[i - 1][2] === nations[i][2] && nations[i - 1][3] === nations[i][3]) {
        nations[i][4] = nations[i - 1][4];
        dup++;
    } else nations[i][4] = nations[i - 1][4] + dup;
}

console.log(nations.find((e) => e[0] === K)[4]);

풀이

우선 각 나라의 금,은,동메달의 개수를 비교하여 정렬한다.
그럼 순위대로 배열이 정렬되고, 정렬된 배열을 순회하며 이전 나라의 메달 개수와 현재 나라의 메달 개수가 일치하다면 중복된 나라의 개수를 뜻하는 dup변수를 1씩 증가시키도록 하고
아니라면 중복된 나라의 개수를 반영하여 현재 나라의 4번 인덱스에 순위를 저장한다.

최종 적으로 모든 나라에 4번 인덱스에 순위를 저장해주고 나면 우리가 찾으려는 K나라의 4번 인덱스를 확인하여 순위를 확인한다.

하지만 이렇게 작성했더니 20점밖에 받지 못했다.

반례를 찾지 못해서 다른 분들의 코드를 보고 풀었다.

해결

dup 변수에 값이 계속해서 누적되기만하고 다시 초기화 되지 않아서 발생한 문제였다.

아래와 같이 입력값이 주어졌을 때

코드를 수행하면 nations 변수의 모양은 이렇게 변한다.

빨간색 네모에 있는 부분이 해당 나라의 순위인데 나라는 5개밖에 없음에도 불구하고 순위는 7위까지 생기는 문제가 발생한다.

따라서 아래와 같이 코드를 수정해주자.

else {
  nations[i][4] = nations[i - 1][4] + dup;
  dup = 1; // 추가된 부분
}

이렇게 하고 실행해보면 nations 변수에 아래 이미지와 같이 정상적으로 순위가 저장된다.

코드(100점)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const nations = input.slice(1).map((e) => e.split(' ').map(Number));
let dup = 1;

nations.sort((a, b) => {
    if (b[1] !== a[1]) return b[1] - a[1];
    else if (b[2] !== a[2]) return b[2] - a[2];
    else return b[3] - a[3];
});

nations[0][4] = 1;
for (let i = 1; i < N; i++) {
    // i-1 번째 나라와 i번째 나라의 메달 수가 같다면
    if (nations[i - 1][1] === nations[i][1] && nations[i - 1][2] === nations[i][2] && nations[i - 1][3] === nations[i][3]) {
        nations[i][4] = nations[i - 1][4];
        dup++;
    } else {
        nations[i][4] = nations[i - 1][4] + dup;
        dup = 1; // 추가된 부분
    }
}

console.log(nations.find((e) => e[0] === K)[4]);

코드(100점)(다른 버전)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const medals = input.slice(1).map((e) => e.split(' ').map(Number));

// 금,은,동이 많은 순서대로 정렬
medals.sort((a, b) => {
    if (b[1] !== a[1]) return b[1] - a[1];
    else if (b[2] !== a[2]) return b[2] - a[2];
    else return b[3] - a[3];
});
// K나라의 인덱스
let idx = medals.findIndex((e) => e[0] === K);

for (let i = 0; i < N; i++) {
    if (JSON.stringify(medals[idx].slice(1)) === JSON.stringify(medals[i].slice(1))) {
        console.log(i + 1);
        break;
    }
}

풀이

위 코드는 메달순으로 정렬하는 코드가 간소화됐다. 메달 수가 다르면 비교하여 메달의 수가 큰 나라가 앞으로 배치되도록 정렬된다.(내림차순 정렬)

medals.sort((a, b) => {
    if (b[1] !== a[1]) return b[1] - a[1];
    else if (b[2] !== a[2]) return b[2] - a[2];
    else return b[3] - a[3];
});

그리고 K나라의 인덱스를 찾고

let idx = medals.findIndex((e) => e[0] === K);

medals 배열을 차례대로 순회하며 만약 K나라와 메달 수가 같을 경우 해당 인덱스+1(K나라의 순위)을 출력한다.

for (let i = 0; i < N; i++) {
    if (JSON.stringify(medals[idx].slice(1)) === JSON.stringify(medals[i].slice(1))) {
        console.log(i + 1);
        break;
    }
}