[정렬] 문제 이름 : 위에서 아래로 - List<E> 정렬, Collections

문제 설명

주어진 수열의 값은 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 작성하시오. 

입력조건)

      첫 째 줄에 수열에 속해 있는 수의 개수 N이 주어짐 ( 1 <= N <= 500)

      둘째 줄부터 N + 1번째 줄까지 N개의 수가 입력됨

      수의 범위는 1 이상 100,000 이하의 자연수

 

사용 개념

가장 기본적인 정렬을 할 수 있는지 물어보는 문제 

 

문제 해결 아이디어

문제의 조건을 보면 수의 개수가 500개 이하로 매우 적으며, 모든 수는 1~100,000 이하이므로 어떠한 정렬 알고리즘을 사용해도 문제를 해결할 수 있음 

 

코드

구현방식)

ㄱ. 입력 받은 값을 ArrayList에 저장하기 위해 리스트 선언 및 생성함 

ㄴ. ArrayList 내림차순 정렬을 위해 Collections 클래스의 reverseOrder()와 sort() 메서드를 사용함

→ 이때 List의 제네릭 타입이 Integer인데, Integer 클래스는 오름차순 정렬을 구현해놓음 (Comparable 인터페이스를 구현하여 compareTo() 메소드를 오버라이딩하여 오름차순 정렬을 구현)

→ Integer 클래스의 메소드를 변경할 수는 없으므로, 내림차순 정렬을 하기 위해서는 내림차순을 구현한 Comparator 타입의 클래스 객체를 sort() 메서드의 인자로 전달해줘야 함

→ 이때 Collections 클래스에서 내림차순을 구현한 Comparator 타입의 클래스 객체를 제공해줌 

    그것이 바로 Collections 클래스의 static 메소드인 reverseOrder() 임! 

Collections 클래스에서 정의되어있는 reverOrder()와 ReverseComparator 클래스

→ Collections 클래스에 정의되어 있는 코드를 보면 reverseOrder()가 Comparator<T> 타입의 객체를 반환함

→ Comparator<T> 인터페이스를 구현한 ReverseComparator 클래스가 compare() 메소드 오버라이딩을 통해 내림차순을 구현함 

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner kbd = new Scanner(System.in);
		
		int N = kbd.nextInt();
		
		List<Integer> arr = new ArrayList<>(); // ㄱ. 리스트 선언 및 생성 
		
		for(int i = 0; i < N; i++) {
			arr.add(kbd.nextInt());
		}
		
		Collections.sort(arr, Collections.reverseOrder()); // ㄴ. 리스트 정렬 
		
		for(int i = 0; i < N; i++)
			System.out.print(arr.get(i) + " ");
		
		kbd.close();
	}

}

 

추가 개념 정리

List<E> 정렬 - 2가지 방식  

→ java.util 패키지의 Collections 클래스의 static method를 사용함

 

선택1) List의 제네릭 타입으로 사용된 클래스에서 정의한 정렬 방식 그대로 사용하는 경우 - 거의 오름차순이 대부분 임  

 

선택2) 내림차순 정렬이나 다른 방식으로 정렬해야 하는 경우 

→ 위의 문제에서처럼 Integer 클래스와 같이 변경 불가능한 클래스들을 제네릭 타입으로 사용할 경우 'Comparator<T> 인터페이스를 구현하여 compare() 메소드를 오버라이딩한 새로운 클래스를 정의하여' 해당 클래스의 객체를 sort()의 인자로 전달해줘야 함 

 

참고)

2021.07.30 - [Algorithm/HackerRank] - [Greedy] 문제 이름 : University Career Fair - 사용자 정의 클래스 객체 정렬

 

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Collections.html