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

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때,

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

---

Solution.java

처음에 이 문제를 해시 없이 이중 반복문으로 문제를 풀었더니 시간 초과로 통과하지 못했었습니다.

이유를 알아보니 이 문제에 "phone_book의 길이는 1 이상 1,000,000 이하"라는 제한사항이있는데

이중 반복문의 경우 시간 복잡도가 O(n2)이기 때문에 phone_book의 길이가 1,000,000일 경우 정말 엄청난 시간이 걸립니다.

 

그래서 Hash를 이용해 풀어야하는데 HashMap을 이용해도되지만 key값만 필요하고 굳이 value는 필요 없기 때문에

같은 전화번호가 중복해서 들어있지 않다는 조건도 있어 HashSet을 이용하여 풀었습니다.

import java.util.HashSet;
import java.util.Set;

public class 전화번호목록 {
    public static void main(String[] args) {
        System.out.println(solution(new String[]{"119", "97674223", "1195524421"}));
        System.out.println(solution(new String[]{"123", "456", "789"}));
        System.out.println(solution(new String[]{"12", "123", "1235", "567", "88"}));
    }

    public static boolean solution(String[] phone_book) {
        boolean answer = true;
        Set<String> book = new HashSet<>();

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

        for (String number : phone_book) {
            for (int i = 1; i < number.length(); i++) {
                if (book.contains(number.substring(0, i))) {
                    answer = false;
                }
            }
        }

        return answer;
    }
}

문제 풀이

1. Set으로 생성한 book에 phone_book의 원소들을 추가합니다.
2. 만약 book에 phone_book의 값들을 돌면서 그 값을 반복문으로 0부터 i까지  잘라보며 일치하는 값이 있는지 확인합니다.
3. 일치하는 값이 있다면 접두어가 있다는 것으로 false를 반환, 아니라면 true를 반환합니다.