글 읽기 - java 답은 나오는데 채점중 3% 근처에서 틀렸다고 나옵니다.

da77777 1년 전 0

java 테스트케이스 여러 개 해봤을 때 답이 나오는데 채점중 3% 근처에서 틀렸습니다! 라고 나옵니다.

어느 부분을 다시 고려해보아야 하는지, 혹은 시도해볼만한 테스트케이스가 있다면 조언 주시면 감사하겠습니다.

테스트케이스는 하단의 4개 외에도 이것저것 해보았는데 답은 다 잘 나왔습니다.

5 2
4 1 2 3 5

5 3
0 1 0 0 0

10 9
10 3 9 8 8 8 8 3 2 4

1 1
-15

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

public class Main {


    public static void quickSelectionSort(int[] arr, int k) {
        quickSelectionSort(arr, 0, arr.length - 1, k);
    }

    public static void quickSelectionSort(int[] arr, int start, int end, int k) {
        if(start >= end) {
            return;
        }

        int leftIndex = start;
        int rightIndex = end;
        int pivotIndex = (start + end) / 2;
        int pivot = arr[pivotIndex];

        while(leftIndex <= rightIndex) {

            while (leftIndex <= pivotIndex && arr[leftIndex] < pivot) {
                leftIndex++;
            }
            while (rightIndex >= pivotIndex && arr[rightIndex] > pivot) {
                rightIndex--;
            }

            if(leftIndex > rightIndex) {
                int temp = arr[leftIndex];
                arr[leftIndex] = arr[pivotIndex];
                arr[pivotIndex] = temp;
            } else {
                int temp = arr[rightIndex];
                arr[rightIndex] = arr[leftIndex];
                arr[leftIndex] = temp;
                leftIndex++;
                rightIndex--;
            }
        }

        if(pivotIndex == k) {
            return;
        }
        else if(pivotIndex > k) {
            quickSelectionSort(arr, start, pivotIndex, k);
        } else {
            quickSelectionSort(arr, pivotIndex+1, end, k);
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }


        quickSelectionSort(arr, k-1);
        System.out.println(arr[k-1]);

    }
}

dldyddlwl 1년 전 0

3 2
15 -15 5

smreo123 1년 전 0

조언드리자면 93%~95%쯤에 퀵셀렉션 최악의 경우를 넣어뒀는지 시간초과로 풀리지 않습니다.

최악의 경우가 nlogn의 경우인 정렬을 활용하여 풀어보시기 바랍니다.

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

문제

문제

출처

ICPC

java 답은 나오는데 채점중 3% 근처에서 틀렸다고 나옵니다.

da77777 1년 전 0

dldyddlwl 1년 전 0

smreo123 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말