[BOJ] 정렬 단계 - JAVA

정렬 단계

• 수 정렬하기
• 수 정렬하기 2

 

▷ 수 정렬하기

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        int testCase = scan.nextInt();
        int[] arr = new int[testCase];
        for(int i = 0; i< testCase; i++){
            arr[i] = scan.nextInt();
        }
        
        for(int i = 0; i < testCase; i++){
            for(int j = i+1; j<testCase; j++){
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        for(int n : arr){
            System.out.println(n);
        }
    }
}

위의 문제를 해결하기 위해서는 삽입 정렬, 버블 정렬, 선택정렬을 사용하여 풀 수 있다.

그 중 나는 가장 간단하다고 생각되는 버블 정렬을 선택하였다. 첫 인덱스 값과 그 다음 값 중 큰 값을 뒤로 보내는 방식이다.

 

▷ 수 정렬하기 2

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int testCase = Integer.parseInt(br.readLine().trim());
        
        List<Integer> arr = new ArrayList<>();
        
        for(int i = 0; i< testCase; i++){
            arr.add(Integer.parseInt(br.readLine().trim()));
        }
        
        Collections.sort(arr);
        
        for(int i : arr){
            bw.write(i+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

처음에는 시간복잡도가 O(NlogN)인 정렬 방법을 사용하여 풀 수 있다고 하여 합병 정렬을 사용했는데 시간초과가 났다. 

첫 시도때 Scanner를 써서 그런가 해서 버퍼를 사용했는데도 시간초과가 뜨길래 문제를 다시 한번 봤더니 뒤에 어려우니 제공되는 함수를 사용하라는 말이 있어서,, 띠용했다.

그래서 리스트의 Collections가 가지고 있는 sort함수를 사용하여 정렬한 것을 출력했다.