글 읽기 - 2751번 퀵 시간초과

je4297 2년 전 0

퀵으로 풀었는데 시간초과가 납니다.

스캐너가 문제라고 해서 bufferedReader랑 bufferedWriter로 바꿨는데도 해결되지 않아 질문을 드립니다.

퀵으로 이 문제가 해결되긴 하는걸까요?

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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());
		}
		
		quickSort(arr, 0, arr.length-1);
		
		for(int i=0; i<n; i++) {
			sb.append(arr[i] + "\n");
		}
		
		
		bw.write(sb.toString());

		br.close();
		bw.flush();
		bw.close();
	}
	
	public static void quickSort(int arr[], int left, int right) {
		if (left > right) {
			return;
		}

		int pivot = left;
		int i = left+1, j = right, temp;

		while (i <= j) {
			while (arr[i] < arr[pivot])   {		// 왼쪽부터 피봇보다 큰 값 찾기 
				i++;
				break;
			}
			while (arr[j] > arr[pivot]) {		// 오른쪽부터 피봇보다 작은 값 찾기 
				j--;
				break;
			}

			if (i > j) {			// 엇갈리면 피봇과 교환 
				temp = arr[pivot];
				arr[pivot] = arr[j];
				arr[j] = temp;
				
			} else {				// 엇갈리지 않으면 왼쪽, 오른쪽 서로 교환 
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		quickSort(arr, left, j-1);
		quickSort(arr, j+1, right);
	}
}

djm03178 2년 전 0

문제 번호를 적는 칸이 따로 있습니다. 거기에 문제 번호를 적어 주세요.

퀵 소트는 최악의 경우 시간복잡도가 O(n^2)입니다. 그리고 그 최악의 경우를 만들기 너무 쉽습니다. 그래서 naive한 퀵 소트는 정렬에 쓰지 않는 것이 좋고, 내장 라이브러리 함수를 쓰는 게 제일 좋습니다.

kipa00 2년 전 0

정말로 이 문제를 퀵 소트로 풀고 싶으시다면,

피봇을 랜덤으로 골라야 합니다. 항상 특정 위치의 피봇을 고르게 구현하는 경우, 쉽게 최악의 경우가 걸리는 테스트 케이스를 만들 수 있기 때문입니다.
피봇과 같은 값은 재귀적으로 처리하지 않도록 해야 합니다. 퀵 소트의 특성상 피봇과 같은 값들은 항상 한쪽 구간으로 쏠리게 됩니다. 따라서 모든 값이 같은 경우 최악의 시간이 걸립니다. 피봇보다 작은 것과 큰 것의 개수를 세어 피봇이 들어갈 위치를 구간으로 찾은 뒤, 그 구간을 모두 피봇과 같은 값이 되도록 자리바꿈한 후 처리하는 것이 좋습니다.

퀵 소트는 시간 복잡도가 n log n의 상수 배일 확률이 매우 높은 것을 이용하는 확률적 알고리즘이기 때문에, 엣지 케이스를 잘 생각해서 그 경우를 모두 처리하게 코드를 작성하셔야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2751번 퀵 시간초과

je4297 2년 전 0

djm03178 2년 전 0

kipa00 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말