[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

---

• 문제

 

 

 

드디어 그동안의 기본정렬을 끝맺는 끝판왕 문제다!

 

 

※ 주의할 점

1. Java 의 시간 제한은 3초다. (원래 자바의 경우 언어 보너스가 있어 주어진 시간의 ×2 + 1 초가 주어지지만 이번에는 3초를 넘길 수 없다)
   (2021. 01. 10 기준 Java → Java8로 명칭이 바뀌었다.)
2. Java 의 메모리 제한은 512MB 이다.

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이전의 수 정렬하기 문제 포스팅을 보셨다면 이 문제는 쉽게 풀 수 있을 것이다.

이 번 문제는 카운팅 정렬을 사용하여 푸는 방법을 사용하라고 있는 것이다. 데이터가 천 만개이고, 데이터의 범위는 10,000 보다 작거나 같은 자연수의 데이터들을 일일이 정렬하려면 시간이 엄청나게 빡빡할 수 밖에 없다.

 

물론 Arrays.sort 를 사용하여 '풀 수'는 있다. 하지만 아슬아슬하게 통과될 것이니.. (사실 최악의 경우 시간복잡도가 O(n²) 까지 나오게 되는데 이번 문제는 저격데이터는 없는 것 같다.)

 

카운팅 정렬에 대해 자세한 것은 아래 두 개 포스팅을 참고하길 바란다.

st-lab.tistory.com/104

카운팅 정렬 (Counting Sort / 계수 정렬) _ Java[자바]

 

 

st-lab.tistory.com/105

[백준] 2750번 : 수 정렬하기 - JAVA [자바]

 

 

 

참고로 카운팅 정렬은 이번의 경우 중복되는 수가 있으니 boolean 배열이 아닌 int 배열을 사용하여 풀 것이다.

 

 

 

 

---

• 2가지 방법을 이용하여 풀이한다.

 

일단 기본적으로 이 문제에서는 입출력의 성능을 좋은 것을 택할 것이다. Scanenr 로 쓰면 내부적으로 자체 정규식 검사 과정에서 시간이 엄청 소요되기 때문에 '시간 초과'가 발생할 수 밖에 없다. 그렇기 때문에 BufferedReader 를 쓰는 것을 디폴트로 해야한다. 또한 출력도 BufferedWriter 또는 StringBuilder 를 이용하여 출력해야한다.

 

방법은 Arrays.sort() 와 Counting 정렬을 쓸 것이다.

 

 

 

---

• 풀이

- 방법 1 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
        
		for(int i = 0; i < N; i++){
			arr[i] = Integer.parseInt(br.readLine());
		}
        
		Arrays.sort(arr);
        
		for(int i = 0; i < N; i++){
			sb.append(arr[i]).append('\n');
		}

		System.out.println(sb);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

먼저 배열에 모든 원소를 입력받아 저장하고 Arrays 패키지에 있는 sort() 를 사용하여 정렬을 한다.

앞서 두 링크의 포스팅을 보셨으면 알겠지만 Arrays.sort() 의 경우 dual-pivot Quick sort 알고리즘을 사용한다. 평균 O(nlogn) 의 시간복잡도를 보이지만 최악의 경우 O(n²) 로 좋지 않는 성능이 될 수도 있음을 알아두셨으면 한다.

 

 

 

 

 

 

 

 

---

- 방법 2 

 

 

Arrays.sort 를 사용하지 않고 카운팅정렬을 사용하는 방법이다.

자세한 것은 코드를 보면서 이해하면 된다. 참고로 시간복잡도는 O(N + K) 이다. K는 자릿수를 의미하는데 입력데이터가 K 보다 훨 씬 큰경우. 즉 데이터가 많으면 많을 수록 O(N) 에 가깝기 때문에 이상적으로는 O(N) 이라고 보아도 무방하다. 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        // 수의 범위 (0 ~ 10000) 사실상 0은 제외
        int[] cnt = new int[10001];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            // 해당 인덱스의 값을 1 증가
            cnt[Integer.parseInt(br.readLine())] ++;
        }

        br.close();

        StringBuilder sb = new StringBuilder();

        // 0은 입력범위에서 없으므로 1부터 시작
        for(int i = 1; i < 10001; i++){
            // i 값이 개수가 0 이 될 때 까지 출력 (빈도수를 의미)
            while(cnt[i] > 0){
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}

 

 

그리 어렵지는 않을 것이다.

다만 중복데이터가 있으므로 누적한 인덱스의 value 값을 한 개씩 줄이면서 0 이 될 때 까지 출력해주어야 한다는 점 잊지 마셔야 한다.

 

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 20122411  -  카운팅 정렬

채점 번호 : 20122409  -  Arrays.sort

 

 

정렬 방식에 따라 확실히 시간차이가 크다는 것을 볼 수 있다.

 

---

• 정리

 

이전 포스팅에서도 카운팅 정렬 방식을 썼던지라 만약 이전 문제들의 글들을 보셨다면 크게 어렵지 않게 풀었으리라 본다.

다만 시간과 메모리 제한이 빡빡하다보니 Collections.sort 를 사용하기 위한 객체(리스트 타입)들은 사용하진 못하고, 입출력도 BufferedReader 와 StringBuilder 혹은 BufferedWriter 을 써야한다는 점이 중요했던 것 같다.

 

필자 생각은 Arrays.sort 로 풀리는지는 몰랐는데.. 문제 데이터를 좀 더 추가했으면 하는 바램..

 

여간 여러가지 정렬방법이 있다는 것을 이 번 기회에 확실하게 배워두셨으면 한다.