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

▪︎ 문제

---

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

▪︎ 알고리즘 설계

---

• Sorting / Loop 활용
  1. 전화번호를 오름차순으로 정렬한다.
     • 예를들어, phone_book[0] = “12”, phone_book[1] = “6”, phone_book[2] = “6789”라고 하자.
     • 0번 인덱스의 값이 1번 인덱스의 값의 접두어가 될 수 있는 경우는 있지만, 0번 인덱스의 값이 1번 인덱스의 값의 접두어가 아닐 경우, 0번 인덱스의 값이 2번 인덱스의 값의 접두어가 될 수 있는 경우는 없다.
     • 그리고, 2번 인덱스의 값이 1번 인덱스의 값의 접두어가 될 수 있는 경우가 없다.
     • 따라서 정렬을 하면 인접한 두 숫자만 비교하면 되고, 앞의 숫자가 뒤의 숫자의 접두어인지만 비교하면 된다.
  2. 한 번의 루프만 돌면서 두 개의 숫자를 비교한다.
  3. 앞의 숫자가 뒤의 숫자의 접두어인지 확인하면 정답을 구할 수 있다.
• Hash 활용
  1. key에 선수 이름, value에 count를 갖는 해시 맵을 만든다.
  2. completion에 존재하는 선수들의 해시를 뺀다.
  3. value가 남아있는 선수가 완주하지 못한 선수이다.

▪︎ 코드

---

• Sorting / Loop 활용

    import java.util.*;
      
    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;
                }
            }
              
            return true;
        }
    }
  

• Hash 활용

    import java.util.*;
      
    class Solution {
        public boolean solution(String[] phone_book) {
            HashMap<String, Integer> map = new HashMap<>();
            for(int i = 0; i < phone_book.length; i++) {
                map.put(phone_book[i], 1); // value 값은 그냥 '전화번호가 1개 존재'라는 의미
            }
              
            for(int i = 0; i < phone_book.length; i++) {
                for(int j = 1; j < phone_book[i].length(); j++) { // phone_book[i]의 길이보다 1번 작게 검토 (같은 전화번호는 없기 때문에!)
                    if(map.containsKey(phone_book[i].substring(0, j)))
                        return false;
                }
            }
      
            return true;
        }
    }
  

▪︎ 시간복잡도

---

• Sorting / Loop 활용: O(N log N + N·M)
• Hash 활용: O(N·M)

▪︎ 틀린 이유

---

• 정렬을 사용했을 때 substring으로 구현했더니, 뒤의 값보다 앞의 값이 길 때 endIndex가 범위를 넘어 StringIndexOutOfBoundsException 발생.
  • 해결: startsWith는 자동으로 길이를 체크해 안전.
  • 또는 substring 사용 시 길이 조건을 먼저 확인해야 함.
• HashMap 풀이 시 value를 전화번호 길이로 저장해도 의미가 없으며, 단순히 존재 여부만 필요하므로 값은 상징적인 1만 사용.
• HashMap 풀이를 처음 생각할 때 모든 접두어를 확인하는 이중 반복문 + containsKey + substring 조합을 떠올리지 못했음.

▪︎ 느낀점 / 기억할 정보

---

• 문자열 처리 시 substring은 항상 인덱스 범위를 고려해야 한다.
  • endIndex > length → StringIndexOutOfBoundsException.
  • 안전하게 처리하고 싶으면 startsWith 같은 메서드 사용.
• HashMap을 사용할 때 value 값은 중요하지 않을 수 있다.
  • 존재 여부 확인에는 key만 필요.
  • key 탐색은 평균 O(1)이므로 빠름.
• 접두어 문제에서 자주 쓰이는 패턴
  • 정렬 후 인접 비교
  • 해시맵에 전체 문자열 저장 후 접두어를 하나씩 검사