알고리즘/백준

[백준 / 구현] 8979 : 올림픽 (python, Javascript)

난감 2024. 6. 19. 10:53
728x90

난이도 : 실버5

문제 설명

문제

올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.

  1. 금메달 수가 더 많은 나라 
  2. 금메달 수가 같으면, 은메달 수가 더 많은 나라
  3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 

각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다. 

각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오. 

입력

입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.

출력

출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다. 

예제 입력 1

4 3
1 1 2 0
2 0 1 0
3 0 1 0
4 0 0 1

예제 출력 1

2

예제 입력 2

4 2
1 3 0 0
3 0 0 2
4 0 2 0
2 0 2 0

예제 출력 2

2

 

풀이 (python)

N, K = map(int, input().split())
medal = []
for i in range(N):
    country = list(map(int, input().split()))
    medal.append(country)

ranking = sorted(medal, key = lambda x : (- x[1], - x[2], - x[3]))

index = 0

for i in range(N):
    if ranking[i][0] == K:
        index = i
        break

rank = index + 1
for i in range(index - 1, -1, -1):
    if ranking[i][1:] == ranking[index][1:]:
        rank -= 1
    else:
        break

print(rank)

 

국가 수 N과 순위를 알고싶은 국가 K를 입력받는다.

medal 배열을 선언하여 이 안에 국가별 금, 은, 동 메달 수를 넣는다.

국가 수 N만큼 for문을 돌면서 county에 국가 번호, 금메달, 은메달, 동메달 수를 리스트 형태로 저장한다. 그리고 이를 medal에 넣는다. (medal은 2차원 배열 형태)

 

medal 배열에 다 넣은 뒤, sorted함수와 lambda를 사용하여 조건에 맞게 정렬한다.

medal[i][0]는 금메달 개수, medal[i][1]는 은메달 개수,  medal[i][2]는 동메달 개수를 뜻하므로 순서대로 내림차순 정렬한다.

ranking = sorted(medal, key = lambda x : (- x[1], - x[2], - x[3]))

파이썬 정렬함수 sorted(배열, 조건)는 배열을 정렬하고 반환한다.

정렬 조건으로 x : ( -x[1], -x[2],  -x[3] ) 처럼 앞에 -를 붙이면 내림차순으로 정렬된다. 그리고 앞에서부터 순서대로 우선순위가 부여된다. 따라서 x[1] 기준으로 정렬이 되고, x[1]의 조건이 같다면 x[2]를 기준으로, x[2]도 같다면 x[3]를 기준으로 정렬한다.

 

찾으려는 국가 K의 순위를 알기 위해 정렬된 ranking 배열에서 국가 K의 위치를 찾는다. 그리고 index 배열에 위치 인덱스 값을 넣는다.

 

한 국가의 랭킹은 (자기보다 순위가 높은 국가 + 1) 이므로 우선 rank를 index +1로 초기화 한다.

국가 K와 모든 메달 수가 같은 국가가 있을 수 있으므로 국가 K의 index - 1 ~ 0 까지 ranking을 돌면서 같은 조건의 국가가 있는지 찾고, 있다면 rank를 -1한다.

같지 않다면 그 위는 더 볼 필요가 없으므로 break한다.

 

위에서 구한 rank를 출력하면 된다.

 

풀이 (Javascript)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './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];
})

const idx = medals.findIndex((e) => e[0] === K);
let rank = idx + 1;

for (let i = idx - 1; i > -1; i--){
    if (JSON.stringify(medals[idx].slice(1)) === JSON.stringify(medals[i].slice(1))){
        rank -= 1;
    } else {
        break;
    }
}

console.log(rank);

 

input 첫번째 줄에서 N, K를 각각 할당한다. map((value) => +value) 를 사용하여 string을 int로 변경했었는데 map(Number)만 적어도 int로 변경이 된다.

 

medals는 각 국가의 번호와 메달의 배열을 저장하는 2차원 배열이다.

input의 첫번째 줄(N,K)을 slice(1)을 사용하여 제외하고, 각 배열을 int로 변환하여 저장한다.

slice() 메서드는 어떤 배열의 begin 부터 end 까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환한다. 원본 배열은 바뀌지 않는다.

 

 

순위는 금메달, 은메달, 동메달 순으로 고려하여 정렬하면 된다. 따라서 sort를 사용하여 medals를 내림차순으로 정렬한다.

 

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에 저장되어 있다. 정렬된 medals 배열에서 findIndex 함수를 이용하여 K의 인덱스를 찾는다. 

 

해당 국가의 등수 rank는 (자신보다 더 잘한 나라 수) + 1로 정의된다.

rank는 K의 인덱스 + 1의 값으로 초기화 한다. 그리고 현재 자신(K)의 인덱스에서 위로 올라가면서 자신과 같은 메달 조건을 가진 나라가 있는지 확인하고, rank를 -1 해준다.

for (let i = idx - 1; i > -1; i--){
    if (JSON.stringify(medals[idx].slice(1)) === JSON.stringify(medals[i].slice(1))){
        rank -= 1;
    } else {
        break;
    }
}

 

medals[idx].slice(1) === medals[i].slice(1) 로 비교하면 항상 false가 뜨기 때문이다. 그 이유는 배열과 배열을 비교할 때 reference 타입으로서 값으로 비교되지 않고 주소값이 비교되는 까닭이다. 따라서 JSON.stringify() 를 사용하여 배열을 문자열로 변경한 뒤 값을 비교해야한다.

JSON.stringify() 메서드는 JavaScript 값이나 객체를 JSON 문자열로 변환한다.

 

메달 조건이 같지 않다면 반복문을 빠져나와 rank를 출력하면 된다.

 

반응형
저작자표시