[Java] 백준 2751번 : 수 정렬하기 2

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

2751번: 수 정렬하기 2

[접근]

일단 이 문제는 값이 중복되지않아 counting sort 로 풀어보았다.

[절댓값이 1,000,000보다 작거나 같은 수 ] 이니까 배열을 1,000,000의 2배로 받아서 인덱스를 이용하여 정렬을 할것이다.

배열의 1,000,000 부터가 0부터 이다.

 

[코드]

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

public class Main2751 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        boolean []arr = new boolean[2000001];

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

        }

        for (int i = 0; i<arr.length;i++){
            if (arr[i]){
                sb.append((i-1000000)).append("\n");

            }
        }
        System.out.print(sb);
    }
}

 

정렬 문제를 계속 접하고있는데 시간초과가 나는 문제들이 몇개씩 생긴다. 여러 정렬들에 대해서 시간복잡도를 정확히 알아야 문제를 풀때

시간초과가 되는 문제를 해결할 수 있을 것같다. 다음에는 정렬에 대해서 공부를 해봐야겠다.