[BOJ 길라잡이/Java] 2일차 #2750 수 정렬하기

알고리즘 분류

- 구현

- 정렬

 

https://www.acmicpc.net/problem/2750

 

브론즈 문제다!

N개의 수를 오름차순 정렬해서 한 줄씩 출력하면 된다.

 

ArrayList에 넣어서 Collections.sort하고 한 줄씩 출력하되

출력할 때 StringBuilder를 사용해서 시간을 줄여야겠다.

라는 생각이 들었고,

그대로 바로 코드를 작성했다.

 

Collections.sort 사용

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

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

        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(br.readLine()));
        } // O(N) 리스트에 추가 ArrayList.add()는 O(1)

        Collections.sort(list); // O(N log N) 팀소트 기반

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(list.get(i));
            if (i != N - 1) {
                sb.append("\n");
            }
        }

        System.out.println(sb.toString());

        
    }
}

 

찾아보니 대부분 List Collections.sort를 하지 않고

array Arrays.sort를 사용했던데, 해당 방법도 사용해 보았다.

 

Arrays.sort 사용

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

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[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        } // O(N) 배열에 값 저장

        Arrays.sort(arr); // O(N log N) 배열 정렬 (퀵소트 기반)

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr[i]);
            if (i != N - 1) {
                sb.append("\n");
            }
        }

        System.out.println(sb.toString());

        
    }
}

 

두 방법 모두 일반적인 경우 O(NlogN) 이므로 큰 차이는 없다.

그러나

QuickSort는 최악의 경우 O(N^2)일 수도 있고,

TimSort는 거의 정렬된 데이터에서 O(N)에 가까워질 수 있다.

 

메모리 사용량 측면에서는 배열이 좋다.

배열(int[])는 연속된 메모리 공간 사용 -> 캐시 효율이 좋고 빠르다.

ArrayList<Integer>는 객체(Integer) 참조를 저장 -> 박싱/언박싱 오버헤드가 있다.

 

내림차순 시

내림차순의 경우

Collections.sort(list, Collections.reverseOrder());

Arrays.sort(arr, Collections.reverseOrder());

이렇게 작성한다.

 

그런데 이때 주의할 점이 있다.

Collections.reverseOrder()로 정렬할 배열은 프리미티브 타입이 아닌 래퍼클래스 이어야 한다.

String, Integer, Double 등과 같은 Object 타입의 배열은 사용이 가능하고,

int, double, char, float 등은 사용이 불가하다.

 

구글링을 통해 이 문제를 풀 수 있는 다른 방법들도 찾아봤다.

 

선택 정렬 (selection sort)

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

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = i+1; j < arr.length; j++ ) {

                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }
}

첫 번째 인덱스와 뒤의 인덱스 값을 비교해서

작으면 앞으로 크면 뒤로 옮기는 작업이고,

시간 복잡도가 O(N^2)라서 좋지는 않다.

 

계수 정렬 (counting sort)

시간 복잡도가 O(N)에 해당하는 빠른 알고리즘이다.

정렬 없이 정렬된 결과를 출력한다.

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

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());
        
        boolean[] arr = new boolean[2001];

        for(int i = 0; i < N; i++) {
            arr[Integer.parseInt(br.readLine()) + 1000] = true;
        }

        for(int i = 0; i < 2001; i++) {
            if(arr[i]) {
                System.out.println(i - 1000);
            }
        }
    }
}

문제 조건에서 절댓값이 1,000보다 작거나 같은 정수가 입력된다고 했으므로

입력값은 -1000부터 1000까지 존재할 수 있다.

 

배열은 음수 인덱스를 사용할 수 없기에,

각 숫자를 양수 인덱스로 변환해야 한다.

즉 -1000은 0번 인덱스, 0은 1000번 인덱스, 1000은 2000번 인덱스에 매핑된다.

 

배열 크기를 2001로 잡고, 해당 위치를 true로 설정하면

숫자가 존재하는지 저장할 수 있다.

 

이 문제처럼

입력값의 범위가 작고 정해져 있을 때,

빠른 정렬이 필요할 때,

숫자의 중복이 없어도 될 때

사용할 수 있다!