글 읽기 - [java] 시간 초과되는 이유를 모르겠습니다.

tn841 6년 전 0

BFS 위상정렬과 dp배열을 활용해 동적계획법으로 풀었습니다.

질문 게시판에 있는 모든 테스트케이스에 대해 정답이 도출되는 것을 확인하였는데요..

채점 33%에서 시간초과되는 이유를 모르겠습니다.

조언해주시면 정말 감사하겠습니다..!

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

public class Main {
	
	//간선을 정의한 클래스
	public static class Line{
		int s;
		int e;
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();	//테스트 케이스
		
		ArrayList<Line> edge = new ArrayList<>();	
		
		for(int ii=0; ii<tc; ii++){
			int n = sc.nextInt();	//노드 수
			int k = sc.nextInt();	//간선 수
			
			int[] cost = new int[n+1];	//노드 별 비용
			int[] dp = new int[n+1];	//dp
			
			for(int i=1; i<n+1; i++){
				cost[i] = sc.nextInt();	//노드의 비용 입력 (index+1)
				dp[i] = cost[i];
			}
			
			for(int i=0; i<k; i++){
				Line line = new Line();
				line.s = sc.nextInt();
				line.e = sc.nextInt();
				edge.add(line);	//간선에 대한 정보를 입력(ArrayList 이용)
			}
			
			int w = sc.nextInt();	//찾고자 하는 값
			
			
			int indegree[] = new int[n+1];	//위상 정렬에서 사용할 indegree 정보를 담은 배열
			for(int i=0; i<k; i++){
				indegree[edge.get(i).e]++;
			}
			
			
			//큐를 이용한 위상정렬 수행 & dp[]배열에 계산 결과 저장
			Queue<Integer> queue = new LinkedList<>();
			for(int i=1; i<=n; i++){
				if(indegree[i] == 0){
					queue.add(i);	//indegree가 0인 것 inqueue
				}
			}
			
			while(!queue.isEmpty()){	//queue가 빌때까지 반복
				int cur = queue.poll();
				//System.out.print(cur+" ");	//bfs 탐색 순서 확인

				for(int i=edge.size()-1; i>=0; i--){
					if(edge.get(i).s == cur){	
						Line line = edge.get(i);
						edge.remove(i);	//간선 제거
						
						
						//dp배열을 활용해 건설 시간 도출 
						if(dp[line.e] > cost[line.e]){
							dp[line.e] = Math.max(dp[line.s] + cost[line.e], dp[line.e]);
						}else{
							dp[line.e] = dp[line.s]+cost[line.e];
						}


						indegree[line.e]--;			//indegree --
						if(indegree[line.e] == 0){
							queue.add(line.e);		//indegree가 0인것은 inqueue
						}
					}
				}
			}//while
			
			System.out.println(dp[w]);
			
		}//for
	}
}

chogahui05 6년 전 1

33%에서 시간초과라..

일단 1번째로.. 가비지가 너무 많이 생겨서

gc가 돌기 때문에 생기는 문제 같습니다. 규칙 수가 10만개까지 되다 보니..

TC 수에 따라서는 충분히 가비지가 많이 쌓일 수 있어요. 일단 이 문제가 있고요.

(arrayLIst에 10만개를 넣으면 실제 메모리 할당 크기는 10만개만큼이 아닙니다. 그보다 더 큽니다)

chogahui05 6년 전 1

더 결정적인 원인이 있습니다.

ArrayList의 remove 함수의 시간 복잡도는 O(n)입니다.

그럴 수 밖에 없는게요. ArrayList는 동적 배열입니다.

앞에 '동적'이라는 말만 붙었지 사실상 배열이기 때문에

특정 위치에서 삽입을 하거나 삭제를 하는 경우에, 뒤에 있는 원소들을 앞으로 당기거나, 뒤로 이동시켜야 합니다.

위 코드에서 ArrayList의 최대 크기는 규칙수인 10만입니다.

60번째 줄에서 79번째 줄을 한 블록으로 봤을 때

바깥에 있는 for문은 10만번.

그리고 안에 있는 remove 함수는 10만번. 이 둘을 곱하면 100억번 나오는군요.

ps.

자잘한 optimize도 필요할 듯 싶군요..

tn841 6년 전 0

상세한 답변 정말 감사합니다.

ArrayList를 사용한것이 문제가 됐군요..

조언해주신 것들 개선해서 해결해보도록 하겠습니다!!!

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

문제

문제

출처

ICPC

[java] 시간 초과되는 이유를 모르겠습니다.

tn841 6년 전 0

chogahui05 6년 전 1

chogahui05 6년 전 1

tn841 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말