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

프로그래머스

 

 

 

이해하기

처음에는 너무 쉽지 않나? 하고 막~ 풀었는데 효율성 빵점 맞았다.

첫 풀이는 이중 for문 돌리면서 자신이 아닌 다른 문자열들을 .startsWith()로 검사했다.

결과는 실패, 시간 초과 ㅜㅅㅜ

제한 사항을 보니 phone_book의 길이가 최대 1,000,000 이라 이중 for문을 돌리면 너무 오래 걸리게 된다.

 

참고한 블로그⬇️

[프로그래머스] 전화번호 목록 (해시 Lv. 2) - 자바 Java

 

• HashMap에 전화번호를 전부 저장한다.
• phone_book을 순회하며 접두어가 존재하는지를 map과 비교하여 찾는다.

예를 들어 {"119", "11954"} 라는 phone_book이 존재한다고 생각해보자.

HashMap에는 다음과 같이 저장될 것이다.

 

이제 phone_book을 순회하며 접두어의 존재 여부를 map과 비교한다.

"119"의 접두어를 찾는 방식은 다음과 같다.

 

앞에서부터 substring하며 해당 값이 map에 존재하는지 비교한다.

접두어이니 119 전체를 비교할 일은 없도록 해야하기에 "1", "11" 까지만 비교한다.

 

 

 

 

그 다음 "11954"를 가지고 접두어의 존재 여부를 확인해보자.

"1"은 map에 없고, "11"도 map에 없는데 "119"는 map에 존재한다.

접두어가 존재하는 것이라고 판단하면 된다.

 

 

 

문제풀이

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < phone_book.length; i++) {
            map.put(phone_book[i], i);
        }

        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))) {
                    return false;
                }
            }
        }

        return answer;
    }
}

 

이번에도 이중 for문이 있는데도 불구하고 시간초과가 나지 않는 이유는 1,000,000 * 1,000,000 이 아니라 1,000,000 * 20 만 하면 되기 때문이다.

(전화번호의 길이는 최대 20이기 때문)