[백준] 수 정렬하기 1,2,3

[백준]의 수 정렬하기, 수 정렬하기 2, 수 정렬하기 3 문제에 대해 Java로 해결한 방법 제시

링크

수 정렬하기

수 정렬하기 2

수 정렬하기 3

---

수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

먼저 수 정렬하기 문제에서는 N의 최대 크기가 1000이다.

자바의 Array.sort() 메소드를 사용하면 쉽게 해결 가능하다.

Array.sort()는 자바에서 기본 제공하는 메소드로, 자체 정렬 알고리즘을 구현 할 필요 없이 sort() 안에 배열만 넣어주면 해당 배열이 정렬되어 나온다.

Array.sort()는 dual-pivot Quciksort 알고리즘을 사용하기에 시간 복잡도는 평균 $O(nlogn)$ 으로 좋은 성능을 낸다.
최악의 경우 $O(n^2)$이기 때문에 일부러 최악의 데이터를 넣을 경우 효율이 떨어질 수 있다.

코드

import java.io.*;
import java.util.Arrays;

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

        int nums[] = new int[N];
        for(int i=0;i<N;i++){
            nums[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(nums); //오름차순 정렬
        
        for(int i=0;i<N;i++){
            System.out.println(nums[i]);
        }
    }
}

---

수 정렬하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

먼저 수 정렬하기 2 문제에서는 N의 최대 크기가 1,000,000이다.
Arrays.sort()로 해결하려고 하면 시간초과가 발생한다. (최악의 데이터를 넣으면 $O(n^2)$의 시간복잡도를 가지기에..)

해결 방법

최악의 경우에도 $O(nlogn)$을 보장하거나, $O(n)$에 가까운 정렬 알고리즘을 사용.

Collections.sort()를 사용.

Collections.sort()은 Timsort 이다. Timsort는 합병 및 삽입 정렬 알고리즘을 사용한다. 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 한다.

합병정렬(Merge sort)는 최선, 최악 모두 $O(nlogn)$을 보장하고, 삽입정렬(Insertion sort)은 최선의 경우 $O(n)$, 최악의 경우 $O(n^2)$이다.

시간복잡도 $O(n)$ ~ $O(nlogn)$을 보장한다.
Collections.sort()를 사용하려면 일반적인 배열이 아닌 List 계열(ArrayList, LinkedList 같은) 자료구조를 사용해서 정렬해야 한다.

코드

import java.io.*;
import java.util.*;

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());

        List<Integer> nums = new ArrayList<Integer>();

        for(int i=0;i<N;i++){
            nums.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(nums);

        for(int i : nums){
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}

---

수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

수 정렬하기 3에서는 추가의 제약조건이 존재한다.

해결

카운팅 정렬/계수 정렬(Counting Sort)을 사용하자.

카운팅 정렬은 시간복잡도가 $O(n)$인 성능이 매우 좋은 알고리즘이다.

왜 시간복잡도가 매우 작을까??
-> 두 수를 비교하는 과정이 없기 때문에 빠른 배치가 가능하다.

단점
: counting 배열이라는 새로운 배열을 선언해주어야 한다.
이 배열은 max 값의 범위의 따라 길이가 결정되는데, 예로 10개의 원소를 정렬하는데 수의 범위가 0~1억이라면 메모리가 매우 낭비가 된다.

코드

import java.io.*;
import java.util.*;

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[] nums = new int[10001]; //최대 배열

        for(int i=0;i<N;i++){
            nums[Integer.parseInt(br.readLine())]++; //숫자 저장
        }

        for(int i=1;i<10001;i++){
            while(nums[i]>0){ //중복 체크
                sb.append(i).append('\n');
                nums[i]--; 
            }
        }
        System.out.println(sb);
    }
}