백준 5052번 (JAVA) 전화번호 목록

 

해싱에 관한 문제이다. 시간이나 메모리 제한이 꽤 여유롭다고 생각하여 처음에는 길이가 짧은 순서대로 정렬한 이후, 

자기 자신을 기준으로 자기 뒤쪽을 StartsWith 메서드를 사용하여 검사하는 식으로 제출하였으나, 시간초과가 생겨 해시를 사용하는 방식으로 변경하였다.

 

1. 문자열을 길이가 긴 순서로 정리한 이후에,

2. 한글자씩 길이를 늘려서 Set에 add하고,

3. 문자열이 변경될때마다 Contains 체크해주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	static List<String> str = new ArrayList<>();
	static Set<String> set = new HashSet<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		int T = stoi(br.readLine());
		loop: for (int tc = 1; tc <= T; tc++) {
			str.clear();
			set.clear();
			int n = stoi(br.readLine());
			for (int i = 0; i < n; i++) {
				str.add(br.readLine());
			}
			str.sort(new Comparator<String>() {
				@Override
				public int compare(String o1, String o2) {
					return o2.length() - o1.length();
				}
			});
			for (String s : str) {
				if (!set.isEmpty()) {
					if (set.contains(s)) {
						System.out.println("NO");
						continue loop;
					}
				}
				for (int i = 0; i < s.length(); i++) {
					set.add(s.substring(0, i));
				}
			}

			System.out.println("YES");
		}

	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

}