백준 2750번 : 수 정렬하기 (Java 8)

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

2750번: 수 정렬하기

설명대로 시간복잡도 허들이 낮은 편인 정렬을 사용해서 풀어봤다. 버블정렬, 삽입정렬, 선택정렬 세 가지로 풀어보았다. Arrays.sort를 사용해도 통과된다.

 

 

버블정렬

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

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];

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

        // Bubble sort
        for(int i = 0; i < arr.length; i++) {
            int idx = -1;
            for(int j = 0 ; j < arr.length - i - 1 ; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
            if(idx ==0)break;
        }
        StringBuilder sb = new StringBuilder();
        for(int each : arr){
            sb.append(each).append("\n");
        }
        System.out.print(sb);

    }
}

 참고 : 자바 공작소 버블정렬 구현

버블정렬 버블소트 BubleSort 자바구현

버블정렬 첫 phase후 마지막 요소는 정렬에서 배제해도 된다는 사실을 이 글을보고 새삼 알았다. 탈출조건을 넣어주니 속도가 조금 올랐다.

 

 

 

삽입 정렬

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];
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        //Insert sort
        for(int i=1; i<N; i++){
            for(int j=i; j>0; j--){
                if(arr[j] < arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int each : arr){
            sb.append(each).append("\n");
        }
        System.out.print(sb);
    }
}

참고 : st님 삽입정렬

자바 [JAVA] - 삽입 정렬 (Insertion Sort)

st님 방식이 효율이 더 좋다. 필요한 부분만 바꾼다.

 

 

 

선택 정렬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
 
		// Select sort
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
		
		for(int each : arr) {
			sb.append(each).append('\n');
		}
		System.out.println(sb);
	}
}