[코딩테스트연습]프로그래머스-[1차] 전화번호 목록 (Lv2)

📝 문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421
  전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

❗ 제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.
• 같은 전화번호가 중복해서 들어있지 않습니다.

🔍입출력 예시

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

---

📌 작성코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Arrays.sort(phone_book); //배열 정렬
        //배열을 정렬하여 비교할려는 문구보다 더 작은 길이의 문자열은 바로 제외하기위해
        
        loop:
        for(int i=0; i<phone_book.length; i++) {
            for(int r=i+1; r<phone_book.length; r++) {
                String str1 = phone_book[i]; //접두사
                String str2 = phone_book[r]; //비교문자열
                
                if((str2.length() >= str1.length()) && (str2.substring(0, str1.length()).equals(str1))) { //비교문자열이 길이가 크고, 접두사로 있다면
                    answer = false;
                    break loop; //탈출
                } else {
                    break; //탈출
                }
            }
        }
        
        return answer;
    }
}

💯Review

코드는 맞았으나, 효율성테스트에서 번번히 시간초과되었다. 그 이유가 접두사가 앞에있는 경우 
바로 찾고 반복문을 탈출하지만, 뒤에 위치하거나, 없는 경우까지의 시간이 오래 걸렸었다.
찾아보니 사전순으로 정렬했으므로 없다면 바로 탈출해도 무방하다는 것을 알았다.

1.배열 정렬
2.이중 반복문으로 접두사와 비교문자열을 저장한다.
3.접두사와 비교문자열을 비교한다

🧾출처

https://school.programmers.co.kr/learn/courses/30/lessons/42577