백준 2822번 점수 계산

개인과제

문제출처: https://www.acmicpc.net/problem/2822

알고리즘: 정렬

 

---

문제

상근이는 퀴즈쇼의 PD이다. 이 퀴즈쇼의 참가자는 총 8개 문제를 푼다. 참가자는 각 문제를 풀고, 그 문제를 풀었을 때 얻는 점수는 문제를 풀기 시작한 시간부터 경과한 시간과 난이도로 결정한다. 문제를 풀지 못한 경우에는 0점을 받는다. 참가자의 총 점수는 가장 높은 점수 5개의 합이다.

상근이는 잠시 여자친구와 전화 통화를 하느라 참가자의 점수를 계산하지 않고 있었다. 참가자의 8개 문제 점수가 주어졌을 때, 총 점수를 구하는 프로그램을 작성하시오.

입력

8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문제, ... 8번 문제이다.

출력

첫째 줄에 참가자의 총점을 출력한다. 둘째 줄에는 어떤 문제가 최종 점수에 포함되는지를 공백으로 구분하여 출력한다. 출력은 문제 번호가 증가하는 순서이어야 한다.

예제 입력

20
30
50
48
33
66
0
64

예제 출력 1

261
3 4 5 6 8

예제 입력 2

20
0
50
80
77
110
56
48

예제 출력 2

373
3 4 5 6 7

예제 입력 3

20
30
50
80
110
11
0
85

예제 출력 3

355
2 3 4 5 8

 

---

선행지식

• 객체 정렬

[Java] 객체 정렬하기 1부 - Comparable vs Comparator

자바 [JAVA] - Comparable 과 Comparator의 이해

 

풀이

1. 문제 번호와 점수를 묶어 Quiz클래스로 만든다.
2. 8개의 점수를 입력받아 Quiz 객체를 만들고(문제번호는 i+1 로 한다) List에 저장한다.
3. 컬렉션에 저장된 Quiz 객체를 정렬
   1. Quiz클래스가 Comparable 인터페이스를 구현한다.( 기본 정렬 기준 설정)
   2. compareTo 메서드를 오버라이딩해 점수를 기준으로 내림차순으로 정렬되도록 한다.
4. 점수 상위 5문제에서 총점, 문제번호를 구해야 한다.
   1. 리스트를 앞에서부터 5개를 잘라 서브리스트틀 만든다.
   2. 총점은 서브리스트의 반복문, 누적합으로 구한다.
   3. 서브리스트를 문제번호를 기준으로 오름차순 정렬한다. (Comparator 람다식 사용)
5. 총점, 서브리스트의 문제번호 출력

코드

import java.util.*;

public class Main {

	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);

		List<Quiz> list = new ArrayList<>();
		int totalScore = 0;							// 총점

		/*------------------------------------------------------------*/
		// 8문제 점수 입력
		for (int i = 0; i < 8; i++) { 
			// 문제번호와 점수로 Quiz 객체를 만들고, list에 저장
			list.add(new Quiz(i+1, scan.nextInt()));
		}

		// 리스트를 기본 정렬 기준(점수 내림차순)에 따라 정렬
		Collections.sort(list);

		// 점수 상위 5개로 서브리스트를 만든다.
		List<Quiz> subList = list.subList(0, 5);
		
		// 총점 구하기 
		for (Quiz quiz : subList) {
			totalScore += quiz.score;
		}

		// 문제 번호를 기준으로 정렬
		Collections.sort(subList, (q1, q2) -> q1.num - q2.num );

		/*------------------------------------------------------------*/
		// 총점과 총점에 포함되는 문제번호 출력
		System.out.println(totalScore);
		
		for (Quiz quiz : subList) {
			System.out.print(quiz.num+" ");
		}
	}
}

class Quiz implements Comparable<Quiz>{
	int num;
	int score;

	public Quiz(int num, int score) {
		this.num = num;
		this.score = score;
	}

	@Override
	public int compareTo(Quiz o) {
		// 기본 정렬 기준: 점수 내림차순 
		return o.score - this.score;
	}

}

Summary

• 일부러 Comparable과 Comparator람다식 둘다 사용해 보았다.