99클럽 코테 스터디 5일차 TIL - [프로그래머스] 전화번호 목록 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 전화번호 목록 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/42577

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : String[] phone_book (1 ≤ phone_book.length ≤ 1,000,000)
출력 : 어떤 번호가 다른 번호의 접두어인 경우가 있는지 여부

가능한 시간복잡도

O(nlogn)

알고리즘 선택

정렬

📌 코드 설계하기

1. phone_book을 정렬한다.
2. 각 전화번호와 다음 전화번호를 startswith로 비교해 접두사 여부를 확인한다.
3. 접두사가 발견되는 false, 없으면 true를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

startswith를 통해 각 문자열을 판단한다.

내일 학습할 것은 무엇인지

구현

📌 정답 코드

정렬 풀이

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                answer = false;
            }
        }
        
        return answer;
    }
}

해시 풀이

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        // 해시맵 생성
        HashMap<String, Integer> map = new HashMap<>();

        // 모든 전화번호를 해시맵에 추가
        for (String phone : phone_book) {
            map.put(phone, 1);
        }

        // 각 전화번호의 모든 접두사가 해시맵에 존재하는지 확인
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                if (map.containsKey(phone.substring(0, i))) {
                    return false;
                }
            }
        }

        // 접두사가 없는 경우 true 반환
        return true;
    }
}