[백준] 5052 전화번호 목록 - JAVA

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

5052번: 전화번호 목록

🌟내가 실수한 부분 
    - 문자열 배열을 Arrays.sort로 정렬하게 되면, 숫자/알파벳 순으로 정렬된다. 
    - 문자열 길이에 따라 정렬된다고 생각했다... 하핫 . 

 

[풀이]

• str1.startsWith(str2) : 문자열 str1이 문자열 str2로 시작한다면 true 반환 
• 모든 문자열을 비교하기에는 O(N^2)로 시간초과가 난다. ▶ 정렬 
• 주어진 문자열을 오름차순으로 정렬하게 되면 숫자 순으로 정렬된다. 
• 전화번호 목록이 오름차순 정렬되어있고, 목록에 있는 전화번호가 같은 경우는 없을 때, 
• 접두어 관계를 가진 두 문자열들은 앞 뒤로 연결되어 있다. 
• 즉, 현재 문자열을 기준으로 '바로 앞의 문자열'을 접두어로 포함하고 있는지만 확인하면 된다. O(N)

ex ) ["123", "567", "1220", "1234"] 가 주어졌을  때 오름차순으로 정렬하게 되면, 
[ "1220", "123", "1234", "567"] 로 정렬된다. 
숫자 순서에 따라 정렬되므로 접두어 관계인 "123" 과 "1234"는 서로 붙어있음. 

 

---

 

[소스 코드]

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)); 
			
		int tc= Integer.parseInt(br.readLine()); //테스트케이스의 갯수
		boolean flag; 
		while(tc-- >0) {
			flag= true; 
			int n= Integer.parseInt(br.readLine()); 
			String phone[] = new String[n];
			for(int i=0; i<n; i++) {
				phone[i] = br.readLine(); 
			}
			
			Arrays.sort(phone);
			
			for(int i=0; i<n-1; i++) {
					if(phone[i+1].startsWith(phone[i])) {
						flag= false; 
						break; 
					}
			}
			
			System.out.println(flag ? "YES" : "NO");
		}
	
	}
}//end of class