백준 5052번
https://www.acmicpc.net/problem/5052

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

예제 입력

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

예제 출력

NO
YES

생각하기

프로그래머스의 "전화번호 목록"과 똑같은 문제입니다.
각 테스트케이스에서 접두어가 있는지만 판단할 수 있으면 됩니다.

동작

먼저 Hashmap을 사용해서 푸는 방법은 전화번호부를 하나 만든다고 생각하고 map을 생성합니다.
그리고 map과번호를 비교할 배열number_list[]도 똑같이 생성해주고,

	if(map.containsKey(number_list[i].substring(0, j))) {
			return false;
	}

number_list[]를 기준으로 map에 포함되는 key값이 있는지 판단해서
접두어가 있는지를 파악합니다.

Arrays.sort를 하는 이유는 짧은 문자열과 앞의 숫자를 기준으로 비교를 하기 위해서 입니다.

앞에 부터 길이가 긴 번호를 오게하면 뒤의 짧은 번호의 접두어 비교가 불가능하게 되기 때문입니다.

배열을 통해 푸는 방법은

	if(number_list[i + 1].startsWith(number_list[i])) {

			return false;
	}

number_list의 앞에 값과 startsWith함수를 사용해서 비교하여
boolean 값을 return 하도록 만들어 줍니다.

Hash map 사용

배열 for문 사용

아무래도 배열을 따로 만들어야 되다 보니,
Hashmap이 메모리와 속도부분에서 떨어질수 밖에 없는것 같습니다.

하지만 2가지 방법을 모두 사용할 줄 안다면, 나중에 또 쓸모가 있을거라고 생각합니다.

TMI

옛날전화기를 쓰는건가??

코드

HashMap 사용

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			int N = Integer.parseInt(br.readLine());
			HashMap<String, Integer> map = new HashMap<>();
			String number_list[] = new String[N];

			for(int i=0; i<N; i++) {
				String str = br.readLine();
				map.put(str, 1);
				number_list[i] = str;
			}

			Arrays.sort(number_list);
			boolean bol = solution(N, number_list, map);

			if(bol == false) {
				sb.append("NO\n");
			}
			else {
				sb.append("YES\n");
			}

		}

		System.out.println(sb);
	} // End of main

	static boolean solution(int length, String[] number_list, HashMap<String, Integer> map) {

		for(int i=0; i<length; i++) {
			for(int j=1; j<number_list[i].length(); j++) {
				if(map.containsKey(number_list[i].substring(0, j))) {
					return false;
				}
			}
		}

		return true;
	} // End of solution
} // End of class

배열 for문 사용

import java.io.*;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			int N = Integer.parseInt(br.readLine());
			String number_list[] = new String[N];

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

			Arrays.sort(number_list);
	
			if(solution(N, number_list)) {
				sb.append("YES\n");
			}
			else {
				sb.append("NO\n");
			}

		}

		System.out.println(sb);
	} // End of main

	static boolean solution(int N, String[] number_list) {

		for(int i=0; i<N-1; i++) {
			if(number_list[i + 1].startsWith(number_list[i])) {

				return false;
			}
		}

		return true;

	} // End of solution
} // End of class