프로그래머스 - 전화번호 목록(Java)

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

처음엔

 

1234

12

321

 

이렇게 들어온다고 가정했을 때 가장 짧은 길이만큼 모두 잘라서 셋에 넣어놓고 판단하면 된다고 생각했다. 그러나 다음과 같은 반례가 존재한다.

 

12

234

2345

 

내 풀이대로 하면 위의 값들은 12, 23, 23 으로 해시값에 들어가 false라고 답할것이다. 사실은 그렇지 않은데 말이다. 완전히 잘못된 로직이다. 그런데 제출했을 때 2가지 케이스 빼고 다 맞아서 어딘가 실수가 있었다고 생각했는데 반례를 보니 완벽히 틀린 코드였다.

 

정해는 다음과 같다.

먼저 모든 값을 셋에 넣어놓는다.

12

234

2345

 

그리고 첫번째 모든 숫자를 길이만큼 잘라 모두 비교한다.

 

12 -> 1, 1

234 -> 2, 23, 23

2345 -> 2, 23, 234, 234

 

전화번호의 길이가 20으로 충분히 짧아서 가능한 풀이로 생각된다. 만약 아주 길었다면 시간초과로 KMP알고리즘이나 라빈카프알고리즘을 사용해야했을 것이다.

 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> set = new HashSet<>();
        
        for(int i = 0; i < phone_book.length; i++){
            set.add(phone_book[i]);
        }
        
        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;
    }
}