글 읽기 - 시간초과때문에 질문드립니다

barcelonamessi 7년 전 0

우선 union find를 하기위해서

U_F라는 클래스를 만들었고 여기서 노드에 해당하는 정보(index, value, name, count)를 저장합니다.

index는 배열에 저장되는 인덱스를 저장하고

value는 배열의 인덱스로 접근하면 얻는 값을 저장하고

name은 이름

count는 루트인경우 현재 모임의 노드 총 개수를 알려줍니다.

우선 name1, name2를 입력 받고

map에서 name1과 name2 가 있는지 찾아봅니다.

그 후에는 1. 둘다 있거나 2. name1만있거나 3. name2만 있거나 4. 둘다 없거나

이 경우에 따라 union을 해주고

그 뒤에 0번인덱스가 포함된 모임의 개수를 찾아서 출력해줍니다.

저는 find 연산의 숫자가 많아서 시간초과가 나는것 같은데 어떻게 해결하면 좋을지 고민중입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	
	static class U_F{
		int index;
		int value;
		String name;
		int count;
		U_F(){}
		U_F(int index,int value,String name, int count){
			this.index=index;
			this.value=value;
			this.name=name;
			this.count=count;
		}
	}

	public static void main(String[] args) throws IOException{
		int T;
		int N;
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer token=new StringTokenizer(in.readLine());
		
		T=Integer.parseInt(token.nextToken());
		for(int i=0; i<T; i++){
			token=new StringTokenizer(in.readLine());
			
			N=Integer.parseInt(token.nextToken());
			U_F[] arr=new U_F[2*N];
			Map<String, U_F> map=new HashMap<String, U_F>();
			
			int count=0;
			int first_index=-1;
			int second_index=-1;
			//저장 정보
			for(int j=0; j<N; j++){
				
				token=new StringTokenizer(in.readLine());
				//한 줄 입력
				U_F first=new U_F();
				U_F second=new U_F();
				String name1, name2;
				name1=token.nextToken();
				name2=token.nextToken();
				//이름 대입
				//1. 배열에서 이름 검색해서 인덱스 알아냄
				
//				first=new U_F(count, name1, 1);
				
				
				
				if(map.containsKey(name1) && map.containsKey(name2)){
					//둘다 이미 있으면
					first=map.get(name1);
					second=map.get(name2);
					
					first_index=map.get(name1).index;
					second_index=map.get(name2).index;
					
					
					
					
					//두 객체가 같은 곳에 없을 경우 유니온 함1
					if(find(first_index, arr)!=second_index &&  find(second_index, arr)!=first_index)
						union(first_index, second_index, arr);
					
					
					
					
				}else if(!map.containsKey(name1) && map.containsKey(name2)){
					//객체 하나 추가하고 유니온
					first=new U_F(count, -1, name1, 1);
					map.put(name1, first);
					
					first_index=count;
					arr[count++]=first;
					
					//second_index=map.get(name2).index;
					second_index=map.get(name2).index;
					

					union(first_index, second_index, arr);
					
					
					
				}else if(map.containsKey(name1) && !map.containsKey(name2)){
					second=new U_F(count, -1, name1, 1);
					map.put(name2, second);
					
					second_index=count;
					arr[count++]=second;
					
					//second_index=map.get(name2).index;
					first_index=map.get(name1).index;
					
					union(first_index, second_index, arr);
				}else{
					//둘 다 없으면 새로운 객체 2개를 추가로 투입해야함.
					first=new U_F(count,-1, name1, 1);
					second=new U_F(count+1,-1, name2, 1);
					
					map.put(name1, first);
					map.put(name2, second);
					
					first_index=count;
					arr[count++]=first;
					second_index=count;
					arr[count++]=second;
					
					union(first_index, second_index, arr);
				}
				
				//System.out.println(arr[0].count);
				System.out.println(arr[find(0, arr)].count);
				//out.write(arr[0].count+"\n");
			}
			//out.close();
			
			
			
		}
	}
	public static void union(int first, int second, U_F[] arr){
		int first_index=find(first, arr);
		int second_index=find(second, arr);
		
		if(arr[first_index].count>=arr[second_index].count){
			//처음 것이 더 크다면 두번째 것을 첫번째 꺼에 더함
			arr[second_index].value=arr[first_index].index;
			arr[first_index].count+=arr[second_index].count;
			
		}else{
			arr[first_index].value=second_index;
			arr[second_index].count+=arr[first_index].count;
			
		}
		
		
	}
	public static int find(int index, U_F[] arr){
		// 가장 루트를 찾음
		int i, last, temp;
		for(i=index; arr[i].value!=-1; i=arr[i].value){
		}
		last=i;
		for(i=index; arr[i].value!=-1; i=temp){
			temp=arr[i].value;
			arr[i].value=last;
		}
		return last; 
		
	}

}

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

문제

문제

출처

ICPC

시간초과때문에 질문드립니다

barcelonamessi 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말