[백준 알고리즘] Q5052 전화번호 목록

1. Java 구현

(1) 시간초과 : 시간복잡도 O(n^2) → 실패

    
import java.io.*;

public 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));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++) {
        	String[] arr = new String[Integer.parseInt(br.readLine())];
        	for(int j = 0; j < arr.length; j++) 
        		arr[j] = br.readLine().replace(" ", "");
        	
        	sb.append(getResult(arr) ? "NO" : "YES").append(System.lineSeparator());
        }
        bw.write(sb.toString());
        bw.close();
	}
	
	public static boolean getResult(String[] arr) {
		for(int i = 0; i < arr.length - 1; i++)
			for(int j = i + 1; j < arr.length; j++) 
				if(arr[j].startsWith(arr[i])) 
					return true;
				
		return false;
	}
}

(2) 문제해결 : 시간복잡도 : O(nlogn) → 성공

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

public 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));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++) {
        	String[] arr = new String[Integer.parseInt(br.readLine())];
        	for(int j = 0; j < arr.length; j++) 
        		arr[j] = br.readLine().replace(" ", "");
        	
        	sb.append(getResult(arr) ? "NO" : "YES").append(System.lineSeparator());
        }
        bw.write(sb.toString());
        bw.close();
	}
	
	public static boolean getResult(String[] arr) {
		Arrays.sort(arr);
		for(int i = 0; i < arr.length - 1; i++)
			if(arr[i + 1].startsWith(arr[i])) return true;
				
		return false;
	}
}

2. 코드설명

 이 문제를 풀때, String.startWith() 메소드를 알고 있으면 좀 더 쉽게 풀 수 있는 문제이다. String.startWith("91")는 해댕 문자열이 "91"로 시작하는지 확인하는 

 메소드이다. "91"로 시작하면 true, 그렇지 않으면 false를 반환한다. 반복문을 통해 문자열을 받으면 문자열의 공백을 반드시 제거해야 한다. 

 그 이유는, 문제의 예시를 보면 "91 12 54 26"은 "911"를 접두어로 가지고 있다고 보기 때문에 문자열의 공백을 replace()메소드로 제거해야 한다.

 이제는 전화번호들이 서로 접두어로 가지고 있는지 확인이 필요하다. 시간초과가난 첫번째 풀이방식은 모든 전화번호들을 서로 비교했기 때문에 시간초과가

 났다. 그래서 시간복잡도를 줄이고자 정렬을 사용했다. (정렬은 시간복잡도 nlogn) 정렬을 사용하면 아래와 같이 정렬된다.

 [911 97625999 91125426] → [911 91125426 97625999] 정렬을 했기 때문에 인접한 전화번호가 가장 비슷한 전화번호이기 때문에 다른 전화번호와 비교할

 필요가 없다. 인접한 전화번호만 비교하면 된다!

3. Pain Point

 예제입력에 나온 예로만 생각을 했기 때문에 공백을 제거해야한다는 생각이 나지는 않았다! 정답률에 비해 생각보다 어렵지 않는 문제였다.

 (아니다.. 운이 좋았다.. 개인적으로 해결되지 않으면.. 일단 정렬해보는 버릇이 있다. 얻어 걸렸다.)