[백준] 2751번 : 수 정렬하기 2 _ JAVA ( 주석 설명 )

1번

→ Collections 클래스의 sort 메소드를 활용한 (오름차순) 정렬

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

//시간 복잡도 : O(n) ~ O(nlog(n))
//공간 복잡도 : 입력할 수만큼의 공간 필요
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()); //입력받을 수의 개수를 입력받는다.

        //Collections.sort 메서드를 사용하기 위해 ArrayList를 사용한다.
        //Array.sort() : 평균 시간복잡도 O(nlog(n)), 최악 O(n^2) => 시간초과
        //Collections.sort() : 평균 시간복잡도 O(n) ~ O(nlog(n))
        ArrayList<Integer> ary = new ArrayList<>();

        for(int i=0;i<N;++i){
            int num = Integer.parseInt(br.readLine());
            ary.add(num); //add : 원소 추가
        }

        Collections.sort(ary); //오름차순으로 정렬

        for(int i=0;i<N;++i){
            sb.append(ary.get(i)).append('\n'); //get : 원소 값 확인
        }

        System.out.println(sb); //정렬된 값 출력
    }
}

 

---

 

2번

→ boolean 배열을 이용한 Counting 정렬

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

public class Main {
    //시간 복잡도 : O(n)
    //공간 복잡도 : 입력값의 범위*2+1 만큼의 공간 필요
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 입력을 위해 버퍼를 이용해 입력을 받는다.
        StringBuilder sb = new StringBuilder(); //빠른 출력 위함

        int range = 1000000; //입력값의 범위는 N<=|range| 이다.
        boolean[] ary = new boolean[range*2+1]; //음수도 인덱스를 이용해 배열에 저장하기 위해서 range*2+1 용량의 배열을 선언했다.

        int N = Integer.parseInt(br.readLine()); //입력받을 수의 개수를 입력받는다.

        for(int i=0;i<N;++i){
            int num = Integer.parseInt(br.readLine());
            ary[num+range] = true; //음수 또한 입력받은 수 + range 로 배열에 저장한다.
        }

        for(int i=0;i<range*2+1;++i){ //0부터 차례대로 검색하기 때문에 자연스럽게 오름차순으로 정렬이 된다.
            if(ary[i])
                sb.append(i-range).append('\n'); //입력받은 수에 한해 StringBuilder에 저장한다.
        }

        System.out.println(sb); //정렬된 값을 출력한다.
    }
}