1주차 프로그래머스 - 전화번호 목록(Lv2)

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

   : 문제의 내용은 프로그래머스 문제를 참고해주세요

프로그래머스

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

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> set_phone = new HashSet<>();
        
        for(String phone_number : phone_book){
            set_phone.add(phone_number);
        }
        
        for(String phone_number: phone_book){
            for(int j = 0; j < phone_number.length(); j++){
            	if(set_phone.contains(phone_number.substring(0,j))){
                    return false;
                }
            }
        }
        
        return true;
    }
}

문제 포인트

  - ... 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return..

 

변수들의 범위

   1) 1 <= 전화번호부 ( phone_book ) <= 1,000,000

   2) 1 <= 전화번호의 길이( phone_number ) <= 20 

 

시간 복잡도

  : N, N^2 => O(N^2) 

    * N: 전화번호부 ( phone_book )의 내용은 set_phone에 입력( 1,000,000 )

    * N^2: 전화번호부 ( phone_book )의 전화번호( phone_number )에서 최대 20번씩 잘라 비교( 1,000,000 * 20 )

       - key를 찾는 과정은 hashMap의 get을 통해 접근하기에 O(1)로 볼 수 있음

    * 최대: 21,000,000

 

알고리즘에서 사용된 관련 메서드

  - contains 내부 작동 원리 확인: https://mydeveloptrace.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9C

자료구조&알고리즘 해시

 

테스트 케이스

  - 전화번호부 ( phone_book ) : 119, 97674223, 1195524421;

  - set_phone : 119, 97674223, 1195524421;

    * 해당 문제에서 set_phone의 용도는 중복 제거가 아닌 key를 확인하는 것에 있음 

  - 전화번호 접두사 : 전화번호.substring(0,j);

  - set_phone.contains는 다음과 같이 표현할 수도 있음

   : set_phone.contains( key )

   : map_phone.containsKey( key )

     * Map<key, value> map_phone = new HashMap<>();

   : map_phone.get( key ) != null 

 

  - 전화번호의 접두사가 포함되었는지 확인 방법

    : for.. 전화번호부 ( phone_book )

          for.. 전화번호 ( phone_number ) = 119

               j = 0; 전화번호 접두사 = x; 

                set_phone.contains(전화번호 접두사)

               j = 1; 전화번호 접두사 = 1;

                set_phone.contains(전화번호 접두사)

               j = 2; 전화번호 접두사 = 11;

                  set_phone.contains(전화번호 접두사)