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

문제 이해

• 전화번호부에 여러 번호가 적혀있다.
• 한 번호가 다른 번호의 접두어인지 확인하려고 한다.

 

<조건>

• 알 수 없음

 

<입력>

• phone_book: 전화번호의 목록 (1 ~ 1,000,000, 10^6)

※ 각 전화번호의 길이는 1 ~ 20

※ 같은 전화번호는 들어있지 않다 -> 중복 X

 

<출력>

• 접두어가 있으면 true, 없으면 false를 리턴하라

 

 

---

문제 풀이

알고리즘 고득점 Kit 해시 태그에 있던 문제이니만큼

처음에는 Hash를 이용한 컬랙션으로 접근했다.

 

 

이 문제는 전화번호라는 하나의 값에 대해서만 다루므로 HashSet을 사용했다.

 

 

핵심 풀이는 다음과 같다.

1. 먼저 HashSet에 전화번호 목록을 넣어놓는다.

Set<String> set = new HashSet<>();
for(String str: phone_book){
    set.add(str);
}

 

 

2. 각 전화번호마다 반복문을 돌린다

for(int i = 0; i < phone_book.length; i++){

 

 

3. 각 전화번호가 "aaba"라면 "a", "aa", "aab"까지 HashSet에 들어있는지 확인한다.

for(int j = 0; j < phone_book[i].length(); j++){
    if(set.contains(phone_book[i].substring(0, j))){
        return false;
    }
}

※ 이때 마지막까지 검사하면 자기 자신을 접두어로 인식하므로 주의하자.

 

 

 

추가 풀이 - Arrays.sort()와 String.startsWith()사용

 

시간 복잡도 상으로는 조금 느리지만

매우 간결한 코드를 다른 사람의 풀이에서 발견했다!

 

 

이 풀이는 String 배열을 정렬할 경우 사전 순으로 정렬된다는 것에서 착안한 풀이이다.

사전 순으로 정렬?
["111", "12", "123", "2"] 이 있을 때
"111"
"12"
"123"
"2"
으로 정렬되는 것.

즉, 같은 자리에 있는 문자로 대소비교를 진행하는 방식!

 

 

1. 먼저 전화번호부를 정렬한다.

Arrays.sort(phone_book);

 

 

2. "바로 다음" 전화번호가 현재의 전화번호로 시작하는지만 확인한다.

※ 사전 순으로 정렬되어있기에 가능!

for(int i = 0; i < phone_book.length-1; i++){
    if(phone_book[i+1].startsWith(phone_book[i])) return false;
}

 

 

---

전체 코드

HashSet 풀이

import java.util.*;

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

 

Arrays.sort와 String.startsWith() 활용 풀이

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;
    }
}

 

 

---

배운 점

String.substring()

Arrays.sort()

String.startsWith()

까지 다양한 메소드의 사용법에 대해 배울 수 있었던 문제였다!