글 읽기 - 병합정렬 정답, 퀵정렬 시간초과에 관한 질문

wnsals1346 1년 전 0

퀵정렬로 2차원배열을 통해 받아왔는데 예상은 했습니다만 시간초과가 떴습니다.
좌표를 2차원배열로 병합정렬을 이용하여 구현했을 때는 700ms로 정답처리됐습니다.
    
궁금한 점은 제 퀵정렬이 잘못된것이 아니라면 이문제는 퀵정렬로 풀 수 없는 것인지 또는 배열말고
좌표를 입력받을만한 간단한 클래스를 구현하면 더가벼워질 수 있을지 궁금합니다!
퀵정렬의 최악의경우가 O(n^2)인것은 알고있습니다만, 평균적인속도면에서 퀵정렬이 nlogn 정렬중에서 좋은 정렬이라고 배웠는데
막상 정렬문제를 풀때는 퀵정렬로 풀리는 문제가 없는 것 같습니다 ㅠㅠ.제가 여러 부분을 놓쳐서 그런건 맞겠지만요.

아직 공부한 정렬은 O(n^2) 정렬이랑 Heap, Merge, Quick O(nlogn) 시간복잡도를 가진 정렬입니다.


읽어주셔서 감사합니다.

package BaekJoonStep.s10;
//https://www.acmicpc.net/problem/11651 - 좌표 정렬하기 2

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

public class P11651 {
    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][2];
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        quickSort(arr, 0, arr.length-1);
        for(int i=0;i<arr.length;i++) {
            sb.append(arr[i][0]).append(" ").append(arr[i][1]).append("\n");
        }
        System.out.println(sb);
    }
    static void quickSort(int[][] arr, int left, int right) {  // x : [i][0], y : [i][1]
        if(left>=right) return;

        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
    static int partition(int[][] arr, int left, int right) {
        int p = right;
        int i = left-1, j = left;
        for(;j<right;j++) {
            if(arr[j][1]<arr[p][1]) {// y값 대소비교
                i++;
                twoDiSwap(arr, i, j);
            } else if (arr[j][1]==arr[p][1]) { // y값이 같은경우
                if(arr[j][0]<=arr[p][0]) { //X값 대소비교
                    i++;
                    twoDiSwap(arr, i, j);
                }
            }
        }
        twoDiSwap(arr, i+1, p);
        return p;
    }
    static void twoDiSwap(int[][] arr, int i, int j) { //2차원배열 교환
        int temp;

        for(int k=0;k<arr[0].length;k++) {
            temp = arr[i][k];
            arr[i][k] = arr[j][k];
            arr[j][k] = temp;
        }
    }

}

wjm7721 1년 전 1

https://www.acmicpc.net/blog/v...

직접 구현한 QuickSort는

피벗을 랜덤으로 잡지 않은 경우

O(N^2)라고 합니다.

wnsals1346 1년 전 1

답변감사합니다. 피벗을 랜덤으로 잡는 퀵소트를 구현해야하는군요. 더욱 공부하도록 하겠습니다 (__)

wnsals1346 1년 전 1

추가로.. 제 피벗코드에도 문제가 있었네요.. 49번라인에 피벗 idx인 p를 리턴하는데 피벗자리를 교체해놓고 그대로 p만 리턴해서

제코드는 무조건 초기에 설정한 right 인덱스를 기준으로 하나씩 배열크기-1번 반복하는 알고리즘이였습니다.. 정렬된 결과만 보고 제대로된 코드라고 생각했었어요.

return p를 return i+1로 고쳐줘야 되는 것 같습니다.

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

문제

문제

출처

ICPC

병합정렬 정답, 퀵정렬 시간초과에 관한 질문

wnsals1346 1년 전 0

wjm7721 1년 전 1

wnsals1346 1년 전 1

wnsals1346 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말