[백준-Java] 정렬 1~3

이번 문제들은 풀었다기보다 공부했다고 봐도 무방하다.
이유는 3가지 모두 같은 문제이지만 다른 방법으로 푸는 문제였기 때문이다.

첫번째 문제를 제외하고는 구글 교수님과 차근차근 배워가는 시간을 가졌다.
시간복잡도의 중요성을 알 수 있는 문제들이었다.

2750번) 수 정렬하기 1

우선 첫번째 문제는 시간복잡도 O(n^2)의 알고리즘으로도 풀 수 있는 문제였다.

빠르게 quick sort를 이용하여 해결하였다.

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));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int tmp;
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++){
            for(int j = i; j < N; j++){
                if(arr[i] > arr[j]){
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        for(int i = 0; i < N; i++) System.out.println(arr[i]);
    }
}

2751번) 수 정렬하기 2

이번 문제는 나중에야 알았지만 시간복잡도 O(Nlogn)의 정렬방법을 이용하는 문제였다.

수업시간에 배운 합병정렬을 다시 공부할 수 있어서 좋았다.
하지만 Java에서는 내장되어있는 메소드가 있기 때문에 그것으로 해결했다.
합병정렬로 다시 풀려다가 머리가 깨지는 줄 알았다...;;

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> list = new ArrayList<>();
        for(int i = 0; i < N; i++) list.add(Integer.parseInt(br.readLine()));
        Collections.sort(list);
        for(int value : list) sb.append(value+"\n");
        System.out.println(sb);
    }
}

10989번) 수 정렬하기 3

마지막 문제는 카운팅 정렬을 사용하는 문제이다.
시간제한은 5초이기 때문에 시간복잡도보다 메모리 용량을 신경쓰는 것이 중요하다.

숫자의 범위는 1~10000이기 때문에 int형 배열을 선언하여 풀이하였다.

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();
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[10001];
        for(int i = 0; i < N; i++) arr[Integer.parseInt(br.readLine())]++;
        for(int i = 0; i < 10001; i++){
            while(arr[i] >0){
                sb.append(i + "\n");
                arr[i]--;
            }
        }
        System.out.println(sb);
    }
}

'카운팅 정렬' 을 처음 들어보아서 생소했지만 막상 풀고나니 자주 쓰던 정렬 방법이었다.

추가로 Arrays.sort()를 사용해서도 이 문제를 풀이할 수 있다.