프로그래머스 - 전화번호 목록(Java)

 

문제 이해는 쉬웠으나 시간복잡도를 고려하면서 구현을 하려니 어려웠다.

 

처음에는 배열의 숫자들을 정수형으로 변형하고, 순회하며 자릿수를 체크하고 그 뒤의 숫자들의 처음부터 차릿수 까지의 숫자가 일치하면 answer를 false로 바꾸면 되겠다 싶어 구현했지만 고려하지 못한 케이스도 있고 시간복잡도 때문에 오답이 생기는 케이스가 생겼다.

 

고려하지 못한 부분

1. 각 숫자의 최대 자리수가 20이므로 이경우 정수형으로 변환 불가
2. 시간 복잡도 O(N^2)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        int[] nums = new int[phone_book.length];
        for(int i=0; i<phone_book.length; i++){
            nums[i]=Integer.parseInt(phone_book[i]);
        }
        Arrays.sort(nums);
        for(int i=0; i<nums.length-1; i++){
            int count=0;
            int m=nums[i];
            while(m>0){ //자릿수 체크
                m/=10;
                count++;
            }
            for(int k=i+1; k<nums.length; k++){
                String str = Integer.toString(nums[k]);
                if(Integer.toString(nums[i]).equals(str.substring(0,count))){
                    answer = false;
                    return answer;
            }
        }
    }
        return answer;
}
}

 

 

startsWith 함수 사용하여 해결

 

입력 문자열 배열을 숫자로 변환하지않고 문자열 그대로 두고 정렬하면 접두사가 비슷한 문자열끼리 붙어있게 된다.

 

따라서 이 경우 한 숫자를 접두사로 가지는 다른 숫자가 있는지 확인 하려면 그 숫자의 바로 뒤 숫자만 확인 하면 된다.

 

startsWith 

 

비교할 문자열.startsWith("체크할 문자열)  

 

문자열의 접두사를 체크할 때 유용하게 쓰이는 메서드를 알게 되었다.

 

 

<정답 코드>

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        for(int i=0; i<phone_book.length-1; i++){
            if(phone_book[i+1].startsWith(phone_book[i])){
                answer=false;
                return false;
            }
        }
        return answer;
}
}

 

 

 

 

---

 

새로운 풀이(2025 - 02 - 25)

 

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String,String> map = new HashMap<>();
        boolean answer = true;
        for(String s : phone_book){
            map.put(s,s);
        }
        
        for(int i=0; i<phone_book.length; i++){
            String a = phone_book[i];
            for(int j=0; j<a.length(); j++){
                if(map.containsKey(a.substring(0,j))){
                    answer=false;
                    return answer;
                }
            }
        }
        return answer;
    }
}