[기업 프로그래밍 콘테스트 예선] 성적이 낮은 순서로 학생 출력하기

문제

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

 

입력 조건

• 첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
• 두 번째 줄부터 N+1 번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

출력 조건

• 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

입력 예시

2
홍길동 95
이순신 77

 

출력 예시

이순신 홍길동

---

아이디어

N이 최대 100,000개 이므로 최소 O(N log N)의 시간복잡도를 보장하는 정렬 알고리즘을 사용해야 한다. 기본적으로 자바의 정렬 라이브러리는 평균 O(N log N)의 시간복잡도를 가지므로, 이를 사용해도 무방하다.

 

- Student 클래스

static class Student {
    String name;
    int score;
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
}

학생 정보를 입력받기 위해 student 클래스를 작성

 

List<Student> students = new ArrayList<>();

for(int i=0; i<N; i++) {
    String[] s = br.readLine().split(" ");
    students.add(new Student(s[0], Integer.parseInt(s[1])));
}

students.sort(Comparator.comparingInt(student -> student.score));

for(Student student : students) {
    System.out.print(student.name + " ");
}

자바의 기본 정렬 라이브러리인 Comparator를 사용해서 학생의 점수를 기준으로 정렬을 실행한다.