[정렬] 이코테 성적 출력(Java)

📚 문제

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

- 시간 복잡도
학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나
O(N)을 보장하는 계수 정렬을 이용하면 된다.

import java.util.*;

class Student implements Comparable<Student>{
	private String name;
	private int score;
	
	public Student(String name, int score) {
		this.name = name;
		this.score = score;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getScore() {
		return score;
	}
	public void setScore(int score) {
		this.score = score;
	}
	
	@Override	
	public int compareTo(Student other) {	//내림차순 정렬
		if(this.score < other.score) {
			return -1;
		}
		return 1;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		List<Student> students = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			String name = sc.next();
			int score = sc.nextInt();
			students.add(new Student(name, score));
		}
		
		Collections.sort(students);
		
		for (int i = 0; i < students.size(); i++) {
            System.out.print(students.get(i).getName() + " ");
        }
	}
}

 

📝 문제 해설

객체 정렬하기

• 객체의 정렬 기준을 정의하는 첫번째 방법은 정렬 대상 클래스를 자바에서 기본적으로 제공하고 있는 Comparable 인터페이스를 구현하도록 변경하는 것

class Student implements Comparable<Student>

• Comparable 인터페이스의 compareTo() 메서드를 통해 인자로 넘어온 같은 타입의 다른 객체와 대소 비교가 가능함. 메서드를 호출하는 객체가 인자로 넘어온 객체보다 작을 경우에는 음수를 리턴하고, 크기가 동일하다면 0, 클 경우에는 양수를 리턴

@Override	
public int compareTo(Student other) {	//내림차순 정렬
	if(this.score < other.score) {
		return -1;
	}
	return 1;
}

• Collections.sort() 메서드에는 Comparable 인터페이스를 구현한 Comparable 타입의 Student 객체의 리스트가 인자로 전달됨

Collections.sort(students);

[출처 : https://www.daleseo.com/java-comparable-comparator/]

 

💡 다른 사람 코드 (HashMap 정렬 아이디어)

public class LowGradeStudent {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        HashMap<Integer, String> student = new LinkedHashMap<>();

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

        List<Integer> scores = student.keySet().stream().sorted().collect(Collectors.toList());

        for(int i = 0; i < scores.size(); i++) {
            System.out.print(student.get(scores.get(i)) + " ");
        }
    }
}

[출처 : https://velog.io/@goshk95 ]