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

문제

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

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

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

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

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

입력

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

출력

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

---

테스트 케이스

 

입력 1

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

출력 1

NO

YES

 

입력 2

1
3
123
1234
12345

출력 2

NO

 

입력 3

1
5
31234443
4443
233123
443
221113

출력 3

YES

---

접근

1. 테스 케이스 숫자를 입력받는다.

2. 번호의 개수를 입력받는다.

3. 번호의 개수만큼 숫자들을 입력받는다.

4. 해당 번호들이 일관성이 있으면 YES출력, 아니면 NO출력

 

4번 과정에서 일관성 있는지 아닌지 판단하는 게 핵심인 듯합니다.

문자열에 있는 숫자를 정렬함으로써, 쉽게 파악할 수 있습니다.

문자열 1245,12456,245를 정렬할 경우,

245,1245,12456 식으로 정렬되지 않고,

1245,12456,245로 정렬되는 것을 이용해야 합니다.

 

따라서, 정렬한 후, 현재 문자열이 다음 문자열과 동일하게 시작하는지 판단하고 맞으면 YES 아니면 NO를 출력합니다.

(12455이 1245로 시작하는지 검사)

245가 12456으로 시작하는지 검사)

 

---

코드

	import java.util.*;
	import java.io.*;
	
	class Main {
	    public static void main(String args[]) throws IOException {
	    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    	
	    	int tc = Integer.parseInt(br.readLine());
	    	for(int tcn=0; tcn<tc; tcn++) {
	    		int n = Integer.parseInt(br.readLine());
	    		TreeSet<String> ts = new TreeSet<>();
	    		boolean resultSwitch = false;
	    		
	    		for(int i=0; i<n; i++) {
	    			ts.add(br.readLine());
	    		}
	    		for(int i=0; i<n-1; i++) {
	    			String temp1 = ts.pollFirst();
	    			String temp2 = ts.first();
	    			if(temp2.startsWith(temp1)) {
	    				resultSwitch = false;
	    				break;
	    			}
	    			resultSwitch = true;
	    		}
	    		bw.write((resultSwitch? "YES":"NO" )+"\n");
	    	}
	    	br.close();
	    	bw.flush();
	    	bw.close();
	    }
	}

 

---

주의

숫자의 정렬과, 문자열 안 숫자의 정렬은 다르다!