백준 - 정렬 2751번 문제 틀린 이유 + 해결

package 정렬.silver;

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] numbers = new int[n];
        int temp = 0;

        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = scanner.nextInt();
        }
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] > numbers[j]) {
                    temp = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = temp;
                }
            }
        }

        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

 

= 다시 =

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(bf.readLine());
        int[] numbers = new int[n];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = Integer.parseInt(bf.readLine());
        }
        int temp = 0;
        int mid = 0;
        int checkPoint = 0;
        int pivot = numbers[0];
        int count = numbers.length - 1;

        for (int i = 1; i < numbers.length - 1; i++) {
            if (checkPoint == 100) {
                break;
            }
            for (int j = count; j > 0; j--) {
                if (pivot > numbers[i]) {
                    continue;
                }

                if (i - j > 0) {
                    mid = j;
                    checkPoint = 100;
                    break;
                }

                if (pivot < numbers[i] && pivot > numbers[j]) {
                    temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
        temp = numbers[mid];
        numbers[mid] = numbers[0];
        numbers[0] = temp;

        for (int i = 0; i < mid; i++) {
            if (i + 1 == mid) {
                break;
            }
            if (numbers[i] > numbers[i + 1]) {
                temp = numbers[i];
                numbers[i] = numbers[i + 1];
                numbers[i + 1] = temp;
            }
        }

        for (int i = mid + 1; i < numbers.length; i++) {
            if (i + 1 == numbers.length) {
                break;
            }

            if (numbers[i] > numbers[i + 1]) {
                temp = numbers[i];
                numbers[i] = numbers[i + 1];
                numbers[i + 1] = temp;
            }
        }

        for (int number : numbers) {
            sb.append(number).append('\n');
        }
        System.out.println(sb);
    }
}

다시 푼 내용을 보면 음.. 시간 초과 때문에 그래서 어떻게 하면 빠르게 정렬을 할 수 있을까 하고 찾아본 내용은 퀵정렬!

 

퀵정렬에 대해 2~3시간 혼자 끙끙 앓고 일단 코드라도 구현을 해보자! 했는데 결국 이것도 시간 초과..

 

더이상 해결 방법이 떠오르지 않아서 구글링을 통해 문제를 해결했다.

 

= 해결 = 

 

음? Collections의 sort 메서드를 이용해서 푸는 것이였다.

 

난 알고리즘을 내가 직접 구현해서 푸는 건 줄 알았는데 그건 아니였나보다.

 

Collections.sort가 가장 빠른 정렬이라고 한다.