문제
도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어졌을 때, 아래의 기준으로 성적순 정렬하는 문제이다.
- 국어 점수가 감소하는 순서로
- 국어 점수가 같으면 영어 점수가 증가하는 순서로
- 국어와 영어 점수가 같으면 수학 점수가 감소하는 순서로
- 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로
입력
첫째 줄에 학생 수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N줄에는 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분되어 주어진다. 점수는 1 이상 100 이하의 자연수이다.
출력
성적 순서대로 학생의 이름을 한 줄에 하나씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 Junkyu 50 60 100 Sangkeun 80 60 50 Sunyoung 80 70 100 Soong 50 60 90 Taewhan 50 60 95 | Sunyoung Sangkeun Junkyu Taewhan Soong |
풀이
4가지 우선순위를 갖는 다중 키 정렬 문제이다. PriorityQueue에 Comparable을 구현한 student 객체를 삽입하여 우선순위에 따라 자동 정렬한다.
- 학생 정보(이름, 국어, 영어, 수학)를
student객체로 파싱하여PriorityQueue에 삽입한다. compareTo메서드에서 국어(내림차순) → 영어(오름차순) → 수학(내림차순) → 이름(사전순) 순으로 비교 규칙을 정의한다.PriorityQueue에서 순서대로 poll하여 이름을 출력한다.
핵심 아이디어: PriorityQueue + Comparable 구현으로 다중 정렬 기준을 표현한다. 국어는 o.kor - this.kor(내림차순), 영어는 this.eng - o.eng(오름차순), 수학은 o.mat - this.mat(내림차순)으로 부호를 구분해야 한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day133BOJ10825국영수 { // 10825
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
PriorityQueue<student> q = new PriorityQueue<student>();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String name = st.nextToken();
int kor = Integer.parseInt(st.nextToken());
int eng = Integer.parseInt(st.nextToken());
int mat = Integer.parseInt(st.nextToken());
q.add(new student(kor, eng, mat, name));
}
while (!q.isEmpty()) {
student tmp = q.poll();
sb.append(tmp.name).append("\n");
}
System.out.println(sb);
br.close();
}
}
class student implements Comparable<student> {
int kor, eng, mat;
String name;
@Override
public int compareTo(student o) {
if (this.kor == o.kor) {
if (this.eng == o.eng) {
if (this.mat == o.mat)
return this.name.compareTo(o.name);
return o.mat - this.mat;
}
return this.eng - o.eng;
}
return o.kor - this.kor;
}
public student(int kor, int eng, int mat, String name) {
super();
this.kor = kor;
this.eng = eng;
this.mat = mat;
this.name = name;
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)