Typiler

알고리즘 문제를 풀다보면 정렬을 해야하는 경우가 많이 발생합니다. 기본적으로 제공되는 Arrays.sort() 함수가 있지만 이것만으로 문제를 풀기에는 한계가 있습니다. 특히 다중차순을 요하는 문제는 직접 구현하는 것이 빠르고 이해가 쉽습니다.

기본적인 정렬 코드

아래는 오름차순, 내림차순, 다중차순의 기본 정렬 구현 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;


class Node implements Comparable<Node>{
	int a;
	int b;
	
	public Node(int a, int b){
		this.a = a;
		this.b = b;
	}

	@Override
	public int compareTo(Node tar) {
		
		// tar 기준으로 tar vs this 중 tar 우선순위가 더 높으면 1
		// tar 기준으로 우선순위가 동등하면 0
		// tar 기준으로 tar vs this 중 tar 우선순위가 더 낮으면 -1
		
		if(tar.a > this.a) return 1;
		if(tar.a < this.a) return -1;
		
		// 첫 수가 우선쉰위가 도등할때 아래 조건을 따른다.
		if (tar.b < this.b) return 1;
		if (tar.b > this.b) return -1;
		
		return 0;
	}
}

public class Sort_ex01 {

	// 정렬
	// 1. 오름차순 
	// 2. 내림차순 
	// 3. 다중차순

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	
    public static void main(String[] args) throws IOException {

        Integer[] arr = {5,4,5,4,4,5};
        
        //1. 오름차순
        Arrays.sort(arr);
        
        //2. 내림차순
        Arrays.sort(arr, Comparator.reverseOrder());
        
        //3. 다중차순
        Node[] arrNode = new Node[6];
        arrNode[0] = new Node(5,8);
        arrNode[1] = new Node(4,2);
        arrNode[2] = new Node(5,1);
        arrNode[3] = new Node(4,9);
        arrNode[4] = new Node(4,7);
        arrNode[5] = new Node(5,3);
        
        // 정렬조건
        // 1) 첫번째 수가 큰수 우선
        // 2) 두번째 수가 작은 수 우선        
        Arrays.sort(arrNode);
        
        int a=1;

		br.close();
		bw.close();

    }
}

오름차순, 내림차순은 Arrays.sort() 함수를 이용하여 구현이 간단합니다. 하지만 다중차순의 경우 정렬 조건이 1) 첫번째 수가 큰수, 2) 두번째 수가 작은 수 우선이라고 한다면 위 코드와 같이 class 를 만들어 Comparable 을 이용하여 구현하여 줍니다. 정렬 우선순위는 compareTo() 함수를 오버라이드 하여 구현하는데, tar 기준으로 tar vs this 중 tar 우선순위가 더 높으면 1,  tar 기준으로 우선순위가 동등하면 0,  tar 기준으로 tar vs this 중 tar 우선순위가 더 낮으면 -1 이 중요합니다. 

이러한 방법을 통하여 "숫자와 문자를 다음과 같은 우선순위 조건으로 맞추어 정렬 후 출력" 하는 문제도 해결이 가능합니다. (ex, 1)짝수 우선 2)숫자 오름차순 3)문자 오름차순)

정렬은 알고리즘에서 응용을 많이 하는 것으로 방법을 꼭 숙지하여야 합니다.