글 읽기 - 질문 게시판에 있는 반례들 외에 다른 반례는 없나요(시간초과 오류)

blue_sau 5년 전 0

1005번 질문 게시판에 있는 반례들은 거의 다 집어 넣어 보았고, 여러 개의 테스트 케이스가 있는 반례들도 잘 돌아가 주었습니다,

그런데, 제출 에서는 시간 초과 오류가 6% 쯤에서 발생하네요.

이 코드에 대한 반례는 없을까요??

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

class BNode {
    int time = 0;
    int preTime = 0;
    public ArrayList<BNode> nodes = new ArrayList<BNode>();   
    
    public BNode(int time){
        this.time = time;
    }
    
    public void addCunnection(BNode target) {
    	nodes.add(target);
    }
    
    public int get_Cunnection_Num() {
    	return nodes.size();
    }
    
    public void cunnect(int prevTime) {
    	if(prevTime > preTime) {
    		preTime = prevTime;
    	}
    }
    
    public int get_Time() {
    	return time + preTime;
    }
    
}



public class Main{


	public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int testCase = scanner.nextInt();
        int[] times = new int[testCase];
        for(int i = 0; i < testCase; i++){
        	int bestTime = -1;
            int numOfBuildings = scanner.nextInt();
            int numOfRules = scanner.nextInt();
            BNode[] buildings = new BNode[numOfBuildings];
            for(int j = 0; j < numOfBuildings; j++){
                buildings[j] = new BNode(scanner.nextInt());
            }  	
            for(int j = 0; j < numOfRules; j++){
               int prev = scanner.nextInt();
               int next = scanner.nextInt();
               buildings[next - 1].nodes.add(buildings[prev - 1]);
            }
            int targetBuilding = scanner.nextInt();
            Queue<BNode> queue = new LinkedList<BNode>();
            queue.add(buildings[targetBuilding - 1]);
            while(!queue.isEmpty()) {
            	BNode temp = queue.remove();
            	boolean isLast = true;
            	for(int k = 0 ; k < temp.get_Cunnection_Num(); k++) {
            		isLast = false;
            		BNode next = temp.nodes.get(k);
            		next.cunnect(temp.get_Time());
                	if(!queue.contains(next)) {
                		queue.add(next);
                	}
            	}
            	if(isLast) {
            		if(bestTime < temp.get_Time()) {
            			bestTime = temp.get_Time();
            		}
            	}
            }
            times[i] = bestTime;
        }
        scanner.close();
        for(int i = 0; i < testCase; i ++) {
        	System.out.println(times[i]);
        }
    }
}

didgogns 5년 전 0

LinkedList.contains()는 O(N)의 시간이 들기 때문에, 이 코드의 시간복잡도는 O(N^2)입니다.

blue_sau 5년 전 0

앗! 그러내요 ㅠㅠ

감사합니다!

blue_sau 5년 전 0

자문 자답입니다.

저 코드 외에도 시간 복잡도를 늘릴만한 요소들이 많아서, 한번 다녀간 곳에 대한 연산은 하지 않는 방식으로 제귀 함수를 이용하여 푸니,

코드도 간단하고 짧아지고, 체감 시간도 많이 줄었습니다. 결국 제귀로 풀었습니다!

저 알고리즘이 틀렸었다기 보다는 시간 복잡도가 높아서 시간 초과가 난 것 같네요.

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

문제

문제

출처

ICPC

질문 게시판에 있는 반례들 외에 다른 반례는 없나요(시간초과 오류)

blue_sau 5년 전 0

didgogns 5년 전 0

blue_sau 5년 전 0

blue_sau 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말