[백준] | JAVA, 자바 | 2751번 - 수 정렬하기 2

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

2751번: 수 정렬하기 2

---

문제 요약 :

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성

(시간 제한 : 2초, 메모리 제한 : 256MB)

---

문제 풀이 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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[] numbers = new int[n];

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

        Arrays.sort(numbers);

        for (int i = 0; i < n; i++) {
            sb.append(numbers[i]).append('\n');
        }
        
        System.out.println(sb);
    }
}

 

1. 수의 개수 n개 입력받기

2. 입력받은 n번 만큼 반복해서 숫자 입력받기

3. 입력받은 숫자를 정렬

4. 정렬된 숫자들을 출력

---

처음 문제를 풀 때, 2750번과 같은 문제인 줄 알았다. 하지만 제출하고 나서 시간 초과로 실패한 걸 확인하고 다른 점을 확인해 봤을 때 입력값이 2750번 보다 범위가 넒은 걸 확인할 수 있었다.

 

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

 

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

 

그렇다면 정렬 알고리즘을 변경해서 시도해야 할까?라는 생각을 해봤는데 혹 출력 방법을 단축시키는 건 어떨까 하는 생각을 해보았다.

그래서 for 문을 사용해 출력하는 방식을 StringBuilder를 사용해 출력해 보았고 결과는 성공이었다.

 

 

하지만 문제의 의도는 Arrays.sort가 아닌 다른 정렬을 사용해서 정렬하는 시간을 단축시키는 의도라고 생각해서 다른 정렬 방식을 사용해 풀어보았다.

---

리팩토링

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

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());
        ArrayList<Integer> numbers = new ArrayList<>();

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

        Collections.sort(numbers);

        for (int i = 0; i < n; i++) {
            sb.append(numbers.get(i)).append('\n');
        }
        System.out.println(sb);
    }
}

 

Arrays.sort() 대신 Collections.sort()를 사용했다.

Arrays.sort()의 경우 시간복잡도가 평균 : O(NlogN), 최악 : O(N^2)이고 Collections.sort()는 평균, 최악 : O(NlogN)이다.

 

Arrays.sort()와 Collections.sort()의 차이점은 시간복잡도 외에도 정렬방식이 다른데 Arrays.sort 같은 경우 배열을 정렬하지만 Collections.sort는 배열이 아닌 리스트를 정렬한다.