[Silver IV] 나는 위대한 슈퍼스타K - 2865 : JAVA

[Silver IV] 나는 위대한 슈퍼스타K - 2865

문제 링크

성능 요약

메모리: 16084 KB, 시간: 144 ms

분류

그리디 알고리즘(greedy), 정렬(sorting)

문제 설명

상근이는 한국 최고의 가수를 뽑는 "나는 위대한 슈퍼스타K"의 감독이다. 상근이는 다음과 같이 참가자를 선발하려고 한다.

"나는 위대한 슈퍼스타K"의 예선에는 N명이 참가했고, 서로 다른 M개 장르에 대한 오디션을 보았다. 심사위원은 모든 참가자의 각 장르에 대한 능력을 점수로 매겼다. 이 점수는 실수로 나타낸다.

본선에는 총 K명이 나갈 수 있다. 각 참가자는 본선에서 단 하나의 장르만 부를 수 있고, 이 장르는 상근이가 정해준다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.

모든 참가자의 각 장르에 대한 능력이 주어진다. 이때, 능력의 합이 최대가 되도록 참가자와 장르를 선택하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. (1 ≤ M ≤ 100, 1 ≤ K ≤ N ≤ 100)

다음 M개의 줄은 각 장르에 대한 참가자의 능력이 주어진다. 이 줄에는 N개의 (i, s)쌍이 주어진다. 여기서 i는 참가자의 번호, s는 그 참가자의 장르에 대한 능력이다. 이 쌍은 능력이 감소하는 순서대로 주어진다. 참가자의 번호는 1부터 N까지 이다.

각 줄에 모든 학생은 한 번씩 등장한다.

출력

첫째 줄에 본선 참가자의 능력의 합을 소수점 첫째자리까지 반올림해 출력한다.

풀이방법

이 문제를 잘 이해하고 쉽게 보기 위해서는 "한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다."는 문장을 잘 보면된다.

1. 즉, M개의 모든 장르들 중에 각 참가자의 번호(1~N)마다 최대값을 기록한다.

2. 내림차순으로 정렬 후, K개 만큼의 합을 구하면, 본선 참가자의 능력의 합을 구할 수 있다.

느낀점

오늘 ArrayList와 LinkedList를 학습하고, 정렬을 배우니 훨씬 쉬운 방법으로 풀 수 있어졌다. 왜냐하면 본선 참가자 K명의 최댓값을 구하기 위해서는 가장 높은 점수를 가진 참가자 K명을 뽑아내야 하는데 내림차순 정렬을 이용한다면 for문을 이용해 순서대로 K개를 뽑아내면 문제를 해결할 수 있기 때문이다.

주의해야할 점은, 파이썬과 다르게 소수점 입력값 따로 타입을 정해줘야하기에 ArrayList와 점수 입력값은 double형으로 입력받아야한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split1 = br.readLine().split(" ");
        int N = Integer.parseInt(split1[0]);
        int M = Integer.parseInt(split1[1]);
        int K = Integer.parseInt(split1[2]);
        
        // N명 만큼
        ArrayList<Double> db = new ArrayList<>();
        for(int i=0;i<N;i++) {
        	db.add(0.0);
        }
        
        // M개의 장르
        for(int i=0;i<M;i++) {
        	String[] split = br.readLine().split(" ");
        	for(int j=0;j<K*2;j+=2) {
        		int idx = Integer.parseInt(split[j])-1;
        		double score = Double.parseDouble(split[j+1]);
        		if(db.get(idx) < score) {
        			db.set(idx, score);
        		}
        	}
        }
        Collections.sort(db, Collections.reverseOrder());

        int cnt = 0;
        double answer = 0;
        for(int i = 0; i < db.size();i++) {
        	answer += db.get(i);
        	cnt++;
        	if (cnt == K) {
        		break;
        	}
        }
        System.out.printf("%.1f",answer);
    }
}