[프로그래머스] Lv2. 전화번호 목록 (HashSet, startsWith, Java)

 

문제설명

입력 & 출력

나의 풀이

이번 문제는 전화번호가 적인 배열 phone_book이 주어질 때 해당 전화번호 북에 한 번호가 다른 번호의 접두사 즉 시작하는 단어에 포함된다면 false를 반환하고, 없다면 true를 반환하는 문제입니다.

 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>();
        
        for(String number : phone_book){
            set.add(number);
        }
        
        for(String number : phone_book){
            for(int i = 1 ; i < number.length() ; i++){
                if(set.contains(number.substring(0,i))){
                    return false;
                }
            }
        }
        return true;
    }
}

 

먼저 Hash문제이기 때문에 HashSet을 이용하여 풀이해 보았습니다. HashMap을 사용하든 HashSet을 사용하든 내부적으로는 HashMap으로 사용하기에 상관이 없습니다.

 

먼저 HashSet을 set의 이름으로 초기화를 해줍니다.

 

그리고 전화번호북을 향상된 for문을 사용하여 순회를 하면서 set에 넣어줍니다.

 

그리고 각 전화번호를 순회하는 데 이때 각요소에 접근하기 위해서 for문을 하나 더 써줍니다.

 

입력받은 전화번호 북의 접두어가 HashSet에 있는지를 확인하면 어떤 번호가 또 다른 번호의 접두어라는 것을 알 수 있게 됩니다.

 

이해가 쉽지않을 수 있습니다. 그러나 다음 예시를 본다면 쉽게 이해가 가능할 것입니다!

 

먼저 전화번호의 접두사는 길이에 따라 다양한 경우가 가능합니다. 예를 들어, 전화번호가 "1195524421"이라고 가정해 본다면 경우의 수는 다음과 같습니다.

 

• "1"
• "11"
• "119"
• "1195"
• "11955"
• "119552"
• "1195524"
• "11955244"
• "119552442"

 

따라서 각 전화번호의 모든 가능한 접두사를 확인하여 접두사 관계를 판단하는 것이 중요합니다.

 

위 예시를 본다면 딱 보면 알 수 있듯이 substring() 메서드를 사용하면 됩니다. 접두어를 체크하는 것 이기 때문에 첫 번째 인자는 0으로 고정되고, 1부터 각 전화번호의 길이만큼 계속해서 반복문을 순회하면서 체크를 합니다.

 

그리고 모든 접두어가 contains()메서드를 사용하여 set에 존재한다면 false를 즉시 return 해주고, 모든 반복문을 돌았는데도 존재하지 않다면 true를 반환하여 마무리해줍니다.

 

 

다른 풀이 ✅

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        // 전화번호 목록을 정렬
        Arrays.sort(phone_book);
        
        // 인접한 번호들만 비교
        for (int i = 0; i < phone_book.length - 1; i++) {
            // 현재 번호가 다음 번호의 접두사인지 확인
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false; // 접두사인 경우 false 반환
            }
        }
        
        // 접두사인 경우가 없는 경우 true 반환
        return true;
    }
}

 

sort() 메서드를 사용하여 sorting을 해주면 다음과 같이 정렬되게 됩니다.

• 정렬 전 : [119, 97674223, 1195524421]
• 정렬 후 : [119, 1195524421, 97674223]

정렬되지 않은 전화번호 목록에서는 각 전화번호를 순서대로 비교하면서 뒤에 나오는 번호가 앞의 번호의 접두사인지를 일일이 확인해야 합니다.

 

그러나 정렬이 됐기 때문에 관련이 있는 즉 숫자가 비슷한 전화번호만 근처에 묶이게 되고, 인접한 전화번호만 확인하고 만약 접두어라면 그 뒤에 전화번호를 확인하지 않아도 되기 때문에 효율적인 비교가 가능합니다.

 

길이가 3이라면 0과 1 비교, 1과 2 비교를 할 것이기 때문에 for문은 0부터 length-1의 조건이어야 인덱스 에러가 발생하지 않습니다.

 

그리고 startsWith() 메서드를 사용하여 해당 전화번호가 접두어인지 확인을 하고 접두어라면 false를 리턴합니다.

 

 

 

 

 

 

참고 ❗

[JAVA] contains() 메소드 알아보기 (문자열 포함 여부 확인)