[백준]2751_수 정렬하기2_Java풀이(Collections.sort, Counting Sort)

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

2751번: 수 정렬하기 2

풀이

• 최대 1,000,000 의 수를 정렬해야함

 

• 자바 내장 정렬 라이브러리 Arrays.sort - 시간복잡도 : 평균 $O(nlogn)$ / 최악 $O(n^2)$ → 시간 초과

• 자바 내장 정렬 라이브러리 Collections.sort - 시간복잡도 : 평균,최악 $O(nlogn)$→ 통과

• 계수 정렬 Counting sort - 시간복잡도 : $O(N+K)$ (N: 데이터의 개수, K: 데이터 중 최대값의 크기)
  (Collections.sort보다 훨씬 빠르고 메모리 효율도 좋음)  → 통과

 

코드

• Collections.sort

package Sorting;

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

public class Main_2751_ {
    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());
        List<Integer> arr = new ArrayList<>();
//        int arr2[] = new int[N];
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(br.readLine()));
//            arr2[i] = Integer.parseInt(br.readLine());
        }

        Collections.sort(arr);
//        Arrays.sort(arr2);
        for (int i = 0; i < N; i++) {
            sb.append(arr.get(i)).append("\n");
//            sb.append(arr2[i]).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

 

 

• Counting Sort

package Sorting;

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

// 계수정렬 Counting sort 사용
// 절대값이 100만 이하인 정수이므로 음수,0이 들어올 수도 있음..
public class Main_2751_2 {
    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());
        // 10 : -1 -2 -3- 4 -5 1 2 3 4 5
        // 홀수자리에 음수를, 짝수자리에 양수를 넣기.
        // 1 2 3 4 5 6 7 8 9 10 ( index )
        // 1 3 5 7 9 => -num => num * 2 -1
        // 2 4 6 8 10 => num => num * 2
        int arr[] = new int [2000001];//new int[N*2+1];
        boolean zero = false;
        for (int i = 1; i <= N; i++) {
            int num = Integer.parseInt(br.readLine());
            if(num<0) arr[num*-2-1]++ ;
            else if(num>0) arr[num*2]++;
            else zero = true;
        }

        for (int i = 2000000; i >= 1 ; i--) {
            if(arr[i] !=0){
                int num = 0;
                if(i%2 != 0){ // 홀수일 경우 => 음수
                    num = ((i + 1) / 2) * (-1);
                    sb.append(num).append("\n");
                }
            }
        }
        if(zero) sb.append(0).append("\n");

        for (int i = 1; i <= 2000000 ; i++) {
            if(arr[i] !=0){
                int num = 0;
                if(i%2 == 0){ // 짝수일 경우 => 양수
                    num = i / 2;
                    sb.append(num).append("\n");
                }
            }
        }
        System.out.println(sb);

    }
}

 

참고

• 참고 코드 - 계수정렬 아주 쉽게…

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));
		StringBuilder sb = new StringBuilder();
        
		/*
		  -1000000 ~ 1000000
		  기준점 0 = index 100000 으로 생각
		*/
		boolean[] arr = new boolean[2000001];	
        
		int N = Integer.parseInt(br.readLine());
        
		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);
	}
}