전화번호 목록

[프로그래머스] 전화번호 목록 - Java 풀이 (TreeSet)

💡 Key Point: 문자열을 사전순(알파벳순)으로 정렬하면, 어떤 번호의 접두어가 되는 번호는 반드시 바로 뒤(인접한 원소)에 오게 됩니다!

---

📌 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

이름	전화번호
구조대	119
박준영	97 674 223
지영석	11 9552 4421

구조대 번호(119)는 지영석의 번호(1195524421)의 접두사입니다. 따라서 이 경우 false를 반환합니다.

⚙️ 제한 사항

• phone_book의 길이: 1 이상 1,000,000 이하
• 각 전화번호의 길이: 1 이상 20 이하
• 같은 전화번호가 중복해서 들어있지 않습니다.

---

🔍 풀이 접근 방식

전화번호 수가 최대 1,000,000개이므로 $O(N^2)$ 형태의 이중 반복문은 시간 초과가 발생합니다.

핵심 아이디어: TreeSet과 사전순 정렬

1. TreeSet을 이용하면 원소를 추가하는 동시에 사전순으로 자동 정렬됩니다.
2. 문자열이 사전순으로 정렬되면 접두어 관계인 문자열들은 반드시 인접해 있게 됩니다.
   • 예: ["119", "1195524421", "97674223"]
3. 따라서 TreeSet.higher(s)를 통해 바로 다음 단어 하나만 startsWith()로 비교하면 충분합니다.

---

💻 Java 코드

```java
import java.util.*;

class Solution {
public boolean solution(String[] phone_book) {
// 사전순 정렬 상태를 유지하는 TreeSet 선언
TreeSet set = new TreeSet<>();

    for (String number : phone_book) {
        set.add(number);
    }

    // 각 번호에 대해 '바로 다음(higher)' 번호와만 접두어 관계인지 확인
    for (String s : set) {
        String next = set.higher(s);
        if (next != null && next.startsWith(s)) {
            return false; // 접두어 발견 시 즉시 false 반환
        }
    }

    return true;
}

 

나에 대한 풀이 

먼저 이게 Set 이 아닌 다른 풀이가 정석인 거 같지만

일단 나는 뭔가 TreeSet 으로 정렬해서 풀면 좋지 않을까 생각해서 이렇게 했다.

다음이 null이 아닌 때 랑(끝이 아닌경우) 와 startsWiths(문자열 비교)가 핵심이다.

그리고 HashSet 정렬이 안되서 다음거를 불러오는 higher는 TreeSet(정렬된것만 사용가능하다.)

참고로 hashSet은 시간복잡도가 O(N)이다.

 

 

import java.io.*;
import java.util.*;

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

 

 

여기서 배열을 꺼내서 문자열을 substring 으로 꺼내서 보는 아이디어가 중요한거 같다.