백준 수 정렬하기 2(2751)

이번에는 정렬 문제를 풀어보려고 문제 하나를 찾았다.

 

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

2751번: 수 정렬하기 2

 

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
4
3
2
1

예제 출력 1 복사

1
2
3
4
5

 

간단하게 정렬하는 문제였다 

근데 풀어보니 시간 초과가 나와서 고생을 좀했던 문제이다.

 

처음에는 간단하게 우선순위 큐를 이용해서 처리해보려했는데 이게 시간 초과가 나왔다 

시간 복잡도 O(nlogn)으로도 안풀린다라... 퀵정렬인가?

 

퀵 정렬 구현해보고 풀어봤는데도 안된다.. 

퀵 정렬은 70%쯤에 안된다.. 아마 그쯤 O(n^2) 최악의 경우가 걸리는거 같다 

 

그럼 어떻게 풀라는거지? 모르겠어 참고조 해봤더니 IO작업 시간을 줄이라는거다...

BufferedReader 쓰라는건데 참 문제가 생각보다 지저분했다 

 

필자는 보통 Scanner 쓰니까 ㅎ..

 

그래서 BufferedReader에 우선 순위 큐를 푸니 풀어졌다.

 

문제풀이

package sort;

import java.io.*;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/2751
 */
public class Q2751 {

    public static void main(String[] args) throws IOException {
        sort();
//        sort2();
    }

    public static void sort() throws IOException {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        for (int i=0 ; i < n; i++) {
            priorityQueue.add(Integer.parseInt(br.readLine()));
        }

        Iterator<Integer> iterator = priorityQueue.iterator();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while (iterator.hasNext()) {
            bw.write(priorityQueue.poll() + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void sort2() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] nums = new int[n];
        for (int i=0 ; i < n; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }
        quickSort(nums, 0, nums.length - 1);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i=0; i < n; i++) {
            bw.write(nums[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void quickSort(int[] nums, int L, int R) {

        int left = L, right = R;
        int pivot = nums[(L + R) / 2];
        int temp;

        while (left <= right) {
            while (nums[left] < pivot) left++;
            while (nums[right] > pivot) right--;

            if (left <= right) {
                temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }

        }

        if (L < right) {
            quickSort(nums, L, right);
        }

        if (left < R) {
            quickSort(nums, left, R);
        }

    }
}

 

 

결과