[백준] 2750 - 수 정렬하기 (Java)

 

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

*해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다.

---

1. 선택정렬

첫 번째 인덱스부터 시작해서 뒤의 인덱스들과 값을 비교하여 최소값들을 앞 순서로 보내는 방법. 시간 복잡도는 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 {
        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[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }

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

 

2. Arrays.sort() 이용하기

자바에서 기본으로 값을 기준으로 정렬해주는 메서드가 되겠다. Dual-pivot QuickSort 알고리즘을 사용하는데 시간 복잡도는 평균 O(nlongn)이다. 아직 퀵 정렬 개념 정리도 안 했는데 대충 두 개의 피봇을 사용해서 퀵 정렬 한다는 것만 파악했다. 이것도 곧 정리해야지.

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

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

        Arrays.sort(arr);

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

 

 

3. 계수 정렬(Counting Sort)

카운팅 정렬은 값을 비교하면서 정렬하지 않고 입력 받은 값을 index로 해서 해당 값의 출현 빈도 수를 체크하고 출력하는 방법인데 우리는 출현 빈도는 아니니까 이 방식을 응용해서 받은 값을 정렬하고 출력해 보겠다. 시간 복잡도는 O(n)으로 매우 빠르다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        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);
            }
        }
    }
}

내가 궁금했던 내용을 고마운 다른 분이 댓글에 이미 물어봐 주셨다. 이건 선생님이 남기신 답변!

왜 boolean 배열의 size가 2001이 될까 궁금했었는데 댓글을 보면서 고개를 끄덕였다. 그래서 인덱스를 찾을 때도 1000을 더해서 true로 값을 설정해주는 거고 배열 중에 true인 값을 찾아서 해당 인덱스에 1000을 뺀 원래 값을 출력해 주는 것이 되겠다.(윤이버셜 영원히 사랑해요) 아무튼 이해 완료!