글 읽기 - 시간초과 질문(java)

xemic 6년 전 0

우선 입력된 값들을 Graph라는 클래스 안의 LinkedList에 계속 저장해주면서 모든 값들을 입력받았습니다.

여기서 Graph클래스 배열을 만들었고, 반복문을 통해 size가 0인것들을 출력해준 다음, 출력한 값과 연결된 노드들의 연결을 끊음으로서 위상정렬을 구현해나갔습니다.

테스트해볼 숫자를 queue를 통하여 뽑아보면서 시간을 최소화하고자 노력을 했는데도 시간초과가 떠서 질문을 드립니다.

어떤 부분에서 시간을 잡아먹는 것인가요..?

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Graph
{
	LinkedList<Integer> myParent = new LinkedList<Integer>();
	void add(int num)
	{
		myParent.add(num);
	}
	void delete(int num)
	{
		if(myParent.indexOf(num)==-1)
			return ;
		myParent.remove(myParent.indexOf(num));
	}
	int size()
	{
		return myParent.size();
	}
}
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int numCnt = sc.nextInt();
		int compareCnt = sc.nextInt();
		Graph graph[] = new Graph[numCnt];
		for(int i=0; i<numCnt; i++)
			graph[i] = new Graph();
		for(int i=0; i<compareCnt; i++)
		{
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph[b-1].add(a);
		}
		boolean firstPrint = true;
		Queue<Integer> testNum = new LinkedList<Integer>();
		for(int i=0; i<numCnt; i++)
		{
			testNum.offer(i);
		}
		while(!testNum.isEmpty())
		{
			int i = testNum.poll();
			if(graph[i].size() == 0)
			{
				if(firstPrint)
					firstPrint=false;
				else
					System.out.print(" ");
				System.out.print(i+1);
				for(int j=0; j<numCnt; j++)
					graph[j].delete(i+1);
			}
			else
				testNum.offer(i);
		}
	}
}

djm03178 6년 전 0

분류에 있는 위상 정렬에 대해 공부해보시면 될 것 같습니다.

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

문제

문제

출처

ICPC

시간초과 질문(java)

xemic 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말