[프로그래머스] 전화번호목록 (자바)

프로그래머스 고득점 Kit: 해시 - 전화번호 목록

문제 설명

"전화번호 목록" 문제는 전화번호 목록이 주어졌을 때, 어떤 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. 예를 들어, 전화번호 "119"는 "1195524421"의 접두어입니다. 전화번호 목록에 접두어 관계가 하나라도 있으면 false를 반환하고, 그렇지 않으면 true를 반환해야 합니다.

문제 접근 방법

1. HashMap 사용: 모든 전화번호를 HashMap에 저장합니다.
2. 접두어 확인: 각 전화번호의 모든 접두어를 확인하면서, 해당 접두어가 HashMap에 존재하는지 검사합니다.

시간 복잡도 분석

• 전화번호의 수를 N, 각 전화번호의 길이를 L이라고 할 때, 시간 복잡도는 O(N * L^2)입니다.
  • 전화번호 목록을 HashMap에 저장하는 데 O(N)
  • 각 전화번호의 모든 접두어를 확인하는 데 O(N * L^2)

해결 방법

아래는 주어진 문제를 해결하는 Java 코드입니다:

package psg.고득점킷트.해시;

import java.util.HashMap;
import java.util.Map;

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

    public boolean solution(String[] phone_book) {
        Map<String, Integer> map = new HashMap<>();

        // 모든 phone 번호를 HashMap에 담기
        for (String phone : phone_book) {
            map.put(phone, 1);
        }

        for (String phone : phone_book) {
            // 전화번호의 길이만큼 순회
            for (int j = 1; j < phone.length(); j++) {
                // 해당 전화번호의 접두어가 key로 존재하는지 확인
                String prefix = phone.substring(0, j);
                if (map.containsKey(prefix)) {
                    return false;
                }
            }
        }

        return true;
    }
}