글 읽기 - 82%에서 시간초과오류

konis123 2년 전 0

우선 제가 푼 방법은

1 3 4 5 6 3 4 8 4 2

이런식으로 있다고 하면, 반복문을 10번 도는데

첫번째 반복을 돌때에는 1이 자기자신을 가리키므로 +10000000을 해주고 끝나고

두번째 반복을 돌떄에는 3->4->5->6->3 이렇게 가리키므로 6->3 되는 부분에서 또 다시 회전을하면서 4->5->6->3 이 부분만 +10000000 을 더해줍니다.

그리고 세번쨰 반복을 돌때에는 10000000보다 값이 크므로 바로 리턴을 하고 빠져나오는 식으로.. 나머지 반복을 쭉 도는데요.

그리고 마지막에 10000000보다 작은 것들의 개수를 세서 출력을 합니다.

일단 테스트케이스는 질문글에있는거 다 해봤는데 다 잘되는거같은데.. 82%에서 시간초과가 나옵니다...

다른분들중에서도 82%에서 시간초과 뜨시는분이 있는거같은데, 그분이랑은 다른 이유인거같고...(제가 잘 이해를 못했을수도있습니다 ㅠㅠ)

위에 코드가 확실히 비효율적이긴해도 O(n) 인거같은데.. 어디가 문제인지 알려주시면 감사하겠습니다 ㅠㅠㅠ

import java.util.LinkedList;
import java.util.Scanner;

public class algo9466 {

	static int[][] students;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
				
		int n = scan.nextInt();
		int[] ans = new int[n];
		
		int[] sn = new int[n];
		for(int i=0;i<n;i++){
			int count = 0;
			sn[i] = scan.nextInt();
			students = new int[sn[i]+1][2];
			
			for(int j=1;j<=sn[i];j++){
				students[j][0] = scan.nextInt();
				students[j][1] = -1;
			}
			
			for(int j=1;j<=sn[i];j++){
				deep(students, students[j][0], j);
			}
			
			for(int j=1;j<=sn[i];j++){
				if(students[j][1] < 10000000){
					//System.out.println(j);
					count++;
				}
			}
			ans[i] = count;
			//System.out.println(count);
		}
		
		for(int i=0;i<n;i++){
			System.out.println(ans[i]);
		}
		
	}
	
	public static void deep(int[][] students, int next, int flag){
		
		if(students[next][1] >= 10000000)	return;
		
		if(students[next][1] == flag){
			students[next][1] += 10000000;
			addValue(students, students[students[next][0]][0], flag);
			return;
		}
		
		
		students[next][1] = flag;
		deep(students, students[students[next][0]][0], flag);
	}

	public static void addValue(int[][] students, int next, int flag){
		
		if(students[next][1] == flag){
			students[next][1] += 10000000;
			addValue(students, students[students[next][0]][0], flag);
		}
		else{
			return;
		}
		
	}
	
}

seico75 2년 전 2

일단 deep 과 addvalue 가 재귀이기 때문에 O(n)은 아닐 것 같습니다.

만일

2, 3, 4, 5, 6, 7, ..., 99999,100000, 100000

즉 마지막만 자기 자신을 찍은 경우,

첫번째에서 모든 수열을 다 돌고, 마지막 하나 제외시키고

두번째에서 모든 수열 다 돌고, 실패하고

세번째에서 모든 수열 다 돌고, 실패하고.............

결국 O(n²) 되는거 아닌가요?

한번 거쳐서 실패한 수들은 다시 팀이 될 수 없지 않나 합니다.

konis123 2년 전 0

아... 감사합니다! 어떤경우에 안되는건지 이제야 알거같네요!

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

문제

문제

출처

ACM-ICPC

82%에서 시간초과오류

konis123 2년 전 0

seico75 2년 전 2

konis123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말