백준(Baekjoon) 2751번 : 수 정렬하기 2 (JAVA) 문제 풀이

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

---

 

🚀문제

 

💬 예제 입력           

5
5
4
3
2
1             

💬 예제 출력

1
2
3
4
5

 

 

🌈 나의 풀이

문제를 보고 당연히 Arrays.sort() 를 사용하려 했지만,, 시간 초과.

퀵 정렬은 평균 시간 복잡도가   O(nlogn)   이지만,  최악의 경우 O(n2)  까지 될 수도 있다.

일부러 퀵 정렬을 못쓰게 하려고 한 데이터가 있는 것 같다. ( 그럼 다른거 쓰면 되지🙃)

 

Merge Sort 사용

X

 

Counting Sort 사용

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        int[] arr = new int[2000001];

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                sb.append(i - 1000000).append('\n');
            }
        }
        System.out.println(sb);
    }
}

배열의 길이를 1,000,000 이 아니고 2,000,000으로 해놓는 이유는 -1,000,000을 입력 받았을 경우에 arr[0] 값에 체크 해놨다가 

다시 출력할때, 0 - 1,000,000를 해주면 처음 입력 받았던 -1,000,000를 출력을 할 수 있도록 두배로 미리 생성을 해놓았다!

 

 

 

Collections.sort() 를 사용

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        ArrayList<Integer> arrayList = new ArrayList<>();

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

        Collections.sort(arrayList);

        for (Integer integer : arrayList) {
            bw.write(integer + "\n");
        }
        bw.flush();
        bw.close();
    }
}