[프로그래머스] 전화번호 목록

소스코드는 Github에서도 확인하실 수 있습니다.

 

[프로그래머스] 전화번호 목록

 

풀이 🚀

우선, 자료구조에 관계없이 풀이하는 방법에 대해서만 이야기해보자.

{"119", "1234", "11911225"}라는 전화번호들이 존재할 때,

우리는 전화번호 목록에 속하는 A, B에 대해 A가 B의 접두사가 되는 A가 있는지를 확인하고 있다면 false를, 없다면 true를 리턴해야한다.

 

먼저, 특정 자료구조를 선언한 뒤 그 자료구조에 각 값들을 모두 넣는다.

그 후, phone_book을 순회, 각 인덱스의 값들을 슬라이싱하며 우리가 넣어둔 자료구조에 그 값을 포함하는 값이 있는지 확인한다.

예를 들자면 아까와 같이  {"119", "1234", "11911225"} 가 자료구조에 들어있을 때,

 

우리는 "119", "1234", "11911225"를 순서대로 순회하며,

"119"에 대해 "11",

"1234"에 대해 "12", "123",

"11911225"에 대해 "11", "119", "1191", "11911", "119112", "1191122"가 해당 자료구조에 속하는지 확인한다.

 

위 경우엔 "11911225"를 슬라이스 했을 때 나오는 "119"가 자료구조에 속하므로, "119"라는 값은 "1191125"의 접두사가 됨을 확인할 수 있고, false를 리턴해야한다.

 

풀이 과정은 그리 어렵지 않지만, 어떤 자료구조를 선택하느냐에 따라 효율성에서 갈리게 된다.

List를 선택할 경우에는 효율성에서 실패하게 되고, HashMap 또는 HashSet을 사용하면 containsKey를 이용하게 되는데, 이 메서드가 조회할 시 O(1)의 복잡도를 가지므로 효율성에서 성공하게 된다.

 

효율성 실패 코드 - List 사용

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashMap<String, Integer> hashMap = new HashMap<>();
        
        for (int i = 0; i < phone_book.length; i++) {
            hashMap.put(phone_book[i], i);
        }
        
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 1; j < phone_book[i].length(); j++) {
                if (hashMap.containsKey(phone_book[i].substring(0,j))) {
                    answer = false;
                    return answer;
                }
            }
        }
        
        return answer;
    }
}

 

효율성 성공 코드 - HashMap 사용

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        List<String> phoneNumbers = new ArrayList<>();
        
        for (int i = 0; i < phone_book.length; i++) {
            phoneNumbers.add(phone_book[i]);
        }
        
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 1; j < phone_book[i].length(); j++) {
                if (phoneNumbers.contains(phone_book[i].substring(0,j))) {
                    answer = false;
                    return answer;
                }
            }
        }
        
        return answer;
    }
}

 

여담이지만 자료구조에서 이렇게 차이가 난다니.. 놀랍구만

오늘 안으로 HashMap 자료구조의 containsKey 구조에 대해 학습하고 여기에 올려야겠당