[자바] 백준 5052번: 전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

첫번째 시도 시간초과 남.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class P5052 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int TestCase = Integer.parseInt(br.readLine());

		for (int T = 0; T < TestCase; T++) {

			boolean result = true;
			int n = Integer.parseInt(br.readLine());
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Long.parseLong(br.readLine());
			}

			Arrays.sort(arr);

			for (int i = 0; i < n - 1 && result == true; i++) {
				int cur_length = (int) (Math.log10(arr[i]) + 1);
				for (int j = i + 1; j < n; j++) {
					int next_length = (int) (Math.log10(arr[j]) + 1);
					int exp = next_length - cur_length;

					if (arr[i] == (int) (arr[j] / Math.pow(10, exp))) {
						result = false;
						break;
					}
				}
			}
			if (result) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}

	}

}

 

O(n^2)이라서 n=10000일 때 O(1억)이 돼서 시간초과가 났을 것 같다.

 

 

답을 확인하고 다시 푼 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class P5052 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int TestCase = Integer.parseInt(br.readLine());

		for (int T = 0; T < TestCase; T++) {

			boolean result = true;
			int n = Integer.parseInt(br.readLine());
			String[] arr = new String[n];

			for (int i = 0; i < n; i++) {
				arr[i] = br.readLine();
			}

			Arrays.sort(arr);

			for (int i = 0; i < n - 1; i++) {

				if (arr[i + 1].startsWith(arr[i])) {
					result = false;
					break;
				}
			}

			if (result) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}

		}

	}
}

startswith라는 메소드가 있는지 처음 알았다.

.

.

String배열에 숫자들을 받은 후 정렬하면

사전순으로 정렬이 되기 때문에

배열을 한 번만 돌면서

나와 내 다음 문자열을 비교해서, 내 문자열이 다음 문자열에 포함되어있는지 판별하면 된다