프로그래머스 전화번호 목록(level 2)

문제 설명

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

입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

이 문제는 해시 카테고리에 있었지만 내가 아직 해시에 익숙하지 않아서인지 해시로 푸는 방법이 떠오르지 않아서 그냥 다른 방법으로 풀었다.

먼저 맨 처음으로 풀었던 코드는

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        String s1 = "";
        String s2 = "";
        
        for(int i = 0; i < phone_book.length - 1; i++){
            for(int j = i + 1; j < phone_book.length; j++) {
                s1 = phone_book[i];
                s2 = phone_book[j];
                
                if(s1.length() < s2.length() && s2.contains(s1)) {
                    answer = false;
                    break;
                }
                
                if(s2.length() < s1.length() && s1.contains(s2)) {
                    answer = false;
                    break;
                }
            }
        }
        return answer;
    }
}

이렇게 .contains() 함수를 사용하여 길이가 짧은 문자열이 긴 문자열에 포함되어 있으면 answer를 false로 바꾸게 하는 코드였는데

테스트케이스 1, 5번에서 실패가 떴다. 한참을 뭐 때문에 뜬건지 생각했는데 contains 함수를 쓰면 접두어가 아닌 경우에도 포함만 되면 false를 내뱉어서 실패가 뜨는 거였다....ㅎ 문제를 잘 기억해야한다...

암튼 그러면 어떻게 하지?했는데 친구가 startsWith 함수를 알려줘서 그것을 이용해서 성공했습니다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        String s1 = "";
        String s2 = "";
        
        for(int i = 0; i < phone_book.length - 1; i++){
            for(int j = i + 1; j < phone_book.length; j++) {
                s1 = phone_book[i];
                s2 = phone_book[j];
                
                if(s2.startsWith(s1)) 
                    return false;
                
                if(s1.startsWith(s2))
                    return false;
            }
        }
        return answer;
    }
}

완료. 근데 사실 한번에 통과한건 아니고

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        String s1 = "";
        String s2 = "";
        
        for(int i = 0; i < phone_book.length - 1; i++){
            for(int j = i + 1; j < phone_book.length; j++) {
                s1 = phone_book[i];
                s2 = phone_book[j];
                
                if(s1.length() < s2.length() && s2.startsWith(s1)) {
                    answer = false;
                   break;
                }
                
                if(s2.length() < s1.length() && s1.startsWith(s2)) {
                    answer = false;
                   break;
                }
            }
        }
        return answer;
    }
}

이렇게 했더니 시간 초과가 떴다. 아마 이중 for문을 써서 시간 효율성이 간당간당한거같다. 언젠간 새로운 코드도 써봐야지...