글 읽기 - 전화번호 목록 문제 시간 초과

hj_d 9년 전 0

전화번호 목록 을 풀고 있는데요.

계속 시간 초과가 떠서 어떻게 해야 하지 고민입니다.

일단 처음에는 스트링으로 입력 받아 배열에 넣고 각 배열을 비교 하는것으로 하였는데 당연히 시간 초과 뜨더라구요.

그래서 이제는 스트링 길이별로 나누어서 길이가 낮은것으로 높은것을 나누게 하였는데 이거 또한 시간 초과가 뜨더라구요.

그런데 이제 더 어떻게 시간을 줄일지 생각이 안되네요... 혹시 제가 생각 한게 잘못된건가요??

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Call call = new Call();
		call.start();
	}

}

class Call {
	Scanner sc = new Scanner(System.in);

	public void start() {
		int n = sc.nextInt();
		String outPut[] = new String[n];
		for (int i = 0; i < n; i++) {
			int k = sc.nextInt();
			String temp[][] = new String[10][k];
			int arr[] = new int [10];
			String s;
			for (int j = 0; j < k; j++) {
				s = sc.next();
				temp[s.length()-1][arr[s.length()-1]]=s;
				arr[s.length()-1]++;
			}
			int m = 0;
			
				for(int j = 0, g = 0; j < 9; g++)
				{				
					if(g < arr[j])
					{
						for(int a = 0, b = j+1; b<10; a++)
						{
							if(a<arr[b])
							{
								if(temp[b][a].startsWith(temp[j][g]))
								{
									outPut[i]="NO";
									m++;
									break;
								}
							}
							else
							{
								a=-1;
								b++;
							}
						}
					
						if(m==1)
						{
							break;
						}
					}
					else
					{
						g=-1;
						j++;
					}
				}
			
			if(m==0)
			{
				outPut[i]="YES";
			}
		}
		for (int i = 0; i < n; i++) {
			System.out.println(outPut[i]);
		}
	}
}

aaa 9년 전 0

사전순으로 정렬하고 앞의 단어와 뒤의 단어를 앞의 단어의 길이 까지만 비교 해보세요!

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

문제

문제

출처

ICPC

전화번호 목록 문제 시간 초과

hj_d 9년 전 0

aaa 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말