글 읽기 - 시간 초과가납니다.

junsong96 1년 전 0

내장 되어있는 정렬 함수를 사용하지 않고

직접 퀵정렬을 구현하면서 문제풀이 하였습니다.

25~26, 30~31 번째 줄을 제외하고는 퀵정렬 기본 알고리즘과 거의 동일하게 작성하였습니다.

어떤 부분에서 시간이 초과되는 것인가요?

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

class times {
    int start;
    int end;

    times(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class N1931 {
    static void quickSort(times x[], int s, int e) {
        if (s >= e)
            return;
        int pivot = s;
        int left = s + 1;
        int right = e;
        while (left <= right) {
            while (left <= e && x[left].end <= x[pivot].end) {
                if (x[pivot].end == x[right].end && x[pivot].start < x[right].start) // 같을 때 시작시간비교
                    break;
                left++; // 피벗보다 큰 값 찾기
            }
            while (right > s && x[right].end >= x[pivot].end) {
                if (x[pivot].end == x[right].end && x[pivot].start > x[right].start) // 같을 때 시작시간비교
                    break;
                right--; // 피벗보다 작은 값 찾기
            }
            if (left > right) {
                times temp = x[pivot];
                x[pivot] = x[right];
                x[right] = temp;
            } else {
                times temp = x[left];
                x[left] = x[right];
                x[right] = temp;
            }
        }
        quickSort(x, s, right - 1); // 왼쪽 파트 정렬
        quickSort(x, right + 1, e); // 오른쪽 파트 정렬
    }

    public static void main(String[] args) throws IOException, NumberFormatException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int cnt = 1, t_line;
        int N = Integer.parseInt(br.readLine());
        times t[] = new times[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            t[i] = new times(a, b);
        }
        quickSort(t, 0, N - 1); // 끝나는 시간이 빠른 순서로 정렬
        t_line = t[0].end;
        for (int i = 1; i < N; i++) {
            if (t[i].start >= t_line) {
                t_line = t[i].end;
                cnt++;
            }
        }
        System.out.println(cnt);
        br.close();
    }
}

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

문제

문제

출처

ICPC

시간 초과가납니다.

junsong96 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말