글 읽기 - 자바 시간초과 질문드립니다.

42desix 5년 전 0

안녕하세요, 한참 고민하다가 도저히 답이 안 나와서 질문 올립니다.

힙 구현하기가 너무 싫어서 바이너리서치로 구현해봤습니다. 삽입시 재귀 이진탐색을 통해 배열리스트에서 들어가야 할 위치를 찾고, 삭제시 배열리스트의 처음이나 끝에 있는 값을 제거합니다.

삭제 연산은 정렬된 배열리스트의 처음이나 끝을 출 O(1)의 시간이 걸립니다. 삽입연산은 이진탐색을 동반하며, 32비트 정수가 입력으로 주어지므로 삽입연산의 시간복잡도는 최악의 경우 log_2(2^32) = 32가 될 것입니다. 이는 두 개의 힙을 썼을 때의 최악의 경우인 2 * log_2(100만) = 40보다 오히려 작은 값입니다. 결국 최악의 경우 100만 * log(2^32) = 3200만번 정도의 연산을 수행하게 될 것으로 예상합니다.

채점을 돌려보면 1%는 통과가 되고, 3%에 가자마자 시간초과가 납니다. 혹시 Operation 객체 생성하는 데 시간이 오래 걸리나 싶어서 배열리스트 2개로도 돌려봤지만 결과는 같았습니다. 어디에서 문제가 생기는걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

import static java.lang.System.gc;

class DualPriorityQueue7662 {
    private class Operation {
        char op;
        int param;

        Operation(char op, int param) {
            this.op = op;
            this.param = param;
        }
    }

    private int mNumCases;
    private int mNumOperations;
    private Queue<Operation> mOperationQueue;
    private ArrayList<Integer> mDPQ;
    private int mQueueSize;

    public DualPriorityQueue7662() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try {
            mNumCases = Integer.parseInt(reader.readLine());
            for (int i = 0; i < mNumCases; i++) {
                init(reader);
                gc();
                processOperations();

                if (mQueueSize == 0) {
                    System.out.println("EMPTY");
                } else {
                    int max = mDPQ.get(mQueueSize - 1);
                    int min = mDPQ.get(0);
                    System.out.println(max + " " + min);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void init(BufferedReader reader) {
        try {
            mNumOperations = Integer.parseInt(reader.readLine());
            mDPQ = new ArrayList<>(mNumOperations);
            mOperationQueue = new LinkedList<Operation>();
            for (int i = 0; i < mNumOperations; i++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                char op = tokenizer.nextToken().charAt(0);
                int param = Integer.parseInt(tokenizer.nextToken());
                mOperationQueue.offer(new Operation(op, param));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void processOperations() {
        mQueueSize = 0;
        for (int i = 0; i < mNumOperations; i++) {
            Operation operation = mOperationQueue.poll();
            char op = operation.op;
            int param = operation.param;
            switch (op) {
                case 'I':
                    addDPQ(param);
                    mQueueSize++;
                    break;
                case 'D':
                    if (mQueueSize == 0) break;
                    if (param > 0) mDPQ.remove(mQueueSize - 1);
                    else mDPQ.remove(0);
                    mQueueSize--;
                    break;
                default:
                    break;
            }
        }
    }

    private void _addDPQ(int minIdx, int maxIdx, int param) {
        int min = mDPQ.get(minIdx);
        int max = mDPQ.get(maxIdx);
        if (param <= min) {
            mDPQ.add(0, param);
            return;
        }
        if (param >= max) {
            mDPQ.add(param);
            return;
        }
        int midIdx = (minIdx + maxIdx) / 2;
        if(midIdx == minIdx) {
            mDPQ.add(1, param);
            return;
        }

        int mid = mDPQ.get(midIdx);
        if (param > mid) _addDPQ(midIdx, maxIdx, param);
        else _addDPQ(minIdx, midIdx, param);
    }

    public void addDPQ(int param) {
        if (mQueueSize == 0) {
            mDPQ.add(param);
            return;
        }
        _addDPQ(0, mQueueSize - 1, param);
    }
}

public class Main {
    public static void main(String args[]) {
        new DualPriorityQueue7662();
    }
}

42desix 5년 전 0

add 연산이 O(N)이 걸리는 걸 간과해서 시간초과 난 것 같습니다. ㅠㅠ

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

문제

문제

출처

ICPC

자바 시간초과 질문드립니다.

42desix 5년 전 0

42desix 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말