[프로그래머스] 전화번호 목록

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

코딩테스트 연습 - 전화번호 목록

 

1. 문제 조건 정리

a) phone_book 배열의 한 요소가 다른 요소의 접두사인지 확인하는 문제입니다.

b) 같은 전화번호가 중복되어 들어있는 경우는 없습니다.

 

2. 입력 데이터

- N = 1,000,000명, 각 요소는 길이 20 이하의 문자열입니다.

- 1초 시간제한이라고 했을 때, O(N) ~ O(NlogN) 이내로 해결해야 합니다.

 

3. 아이디어

- 배열을 순회하며

- 해당 요소가 다른 요소의 접두사인지 확인합니다.

- 또는 해당 요소가 다른 요소를 접두사로 가지는 지 확인합니다.

- 저는 후자의 방법을 선택했습니다.

- 검색 속도 향상을 위해 해시 테이블을 생성합니다.

 

4. 디버깅

- 접두사의 정의에 따라 현재 요소의 길이 - 1 까지 슬라이싱해야 합니다.

- 그렇지 않으면 자기 자신이 검색되어 항상 접두사가 존재하는 것과 같게 됩니다.

 

5. 구현

- 해시 테이블 생성 후

- 슬라이싱한 문자열에 대한 검색을 하고

- 있는 경우 바로 False를 리턴하고, 해당 사항 없으면 True를 반환한다.

 

- [테이블 생성 O(N) + 순회 및 접두사 검색 O(N)] = O(N) 입니다.

 

6. 문법

- zip : 일종의 교집합 배열을 만들어주는 라이브러리라 이해했습니다.

- str.startswith : prefix 인지를 찾을 때에 편합니다.

 

7. 코드

def solution(phone_book):
    answer = True
    mem = set(phone_book)
    for num in phone_book :
        for i in range(1,len(num)):
            if num[:i] in mem :
                return False
    return answer

 

8. 추가사항

- 접두사 검색 시 사용하는 tmp(코드 내에서 num[:i])를 어떻게 구현하는 게 빠른지 확인이 필요합니다.

- num[:i]와

- tmp = ""로 두고 tmp += num[i] 의 속도 비교가 필요합니다.