[Algorithm] 정렬 (Sort)

1. 조건

(1) 정렬 조건이 필요하다.

• Comparable 인터페이스를 구현해야 한다.
• compareTo 메소드 오버라이딩을 통해 정렬 조건을 구현한다.

(2) 시간 복잡도는 약 O(N logN) 이다.

N개의 원소를 정렬하는 것은 O(NlogN) 만큼의 시간 복잡도를 갖는다.

(3) In-place / Stable 여부를 알아야 한다.

• 정렬 알고리즘이 In-place(제자리)한가?
  • 정렬하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가?
• 정렬 알고리즘이 Stable(안정)한가?
  • 동등한 위상의 원소들의 순서 관계가 보전되는가?
  • ex) 5 3 4 5 수열의 경우
    • 3 4 5 5 => 동등한 위상의 원소들의 순서가 보전되었다.

 

2. 특성

• 코딩테스트에서 정렬은 문제에 직접 언급되지 않는다.
• 아래에 있는 특성을 생각해서 알아차려야한다.

(1) 같은 정보는 인접해 있을 것이다.

(2) 각 원소마다, 가장 가까운 원소는 자신의 양 옆 중에 있다.

 

Example) [BOJ] 10825: 국영수

10825번: 국영수

1) 문제

• 국어 점수가 감소하는 순서
• 아니면 영어 점수가 증가하는 순서
• 아니면 수학 점수가 감소하는 순서
• 아니면 이름이 사전 순으로 증가하는 순서

2) 시간복잡도

• 정렬 => NlogN 시간복잡도를 가진다.

NlogN <= 100,000 * log100,000 = 1,600,000

컴퓨터가 1초에 보통 1억 번 계산하므로 1초 안에 충분히 가능하다.

3) 구현

public class S5_10825 {
    static int N;
    static Performance[] performances;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        performances = new Performance[N];
        for (int i = 0; i <N; i++) {
            String str = br.readLine();
            st = new StringTokenizer(str, " ");
            performances[i] = new Performance(st.nextToken(), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(performances);
        for (int i = 0; i <N; i++) {
            System.out.println(performances[i].name);
        }
    }

    static class Performance implements Comparable {
        String name;
        int korean;
        int english;
        int math;

        public Performance(String name, int korean, int english, int math) {
            this.name = name;
            this.korean = korean;
            this.english = english;
            this.math = math;
        }

        @Override
        public int compareTo(Object o) {
            Performance p = (Performance) o;
            if(this.korean != p.korean) {
                return p.korean - this.korean;
            } else {
                if(this.english != p.english) {
                    return this.english - p.english;
                } else {
                    if(this.math != p.math) {
                        return p.math - this.math;
                    } else {
                        return this.name.compareTo(p.name);
                    }
                }
            }
        }
    }
}