반응형
프로그래머스의 레벨 2 문제 전화번호목록
문제 요구 조건
접두어가 리스트에 포함되는지 비교해야한다.
내 풀이 방법
- 문자열 비교에 걸리는 시간을 단축하기 위해서 해시테이블에 저장하고, 모든 접두어를 만들어서 n*m으로 해결했다.
# 모든 가능한 접두어를 해시테이블에 저장하고 비교하면 n*m. 범위가 작아서 가능
def solution(phone_book):
d = {phone[:i]: True for phone in phone_book for i in range(1, len(phone))}
for phone in phone_book:
if d.get(phone, False):
return False
return True
다른 풀이 방법
문자열을 사전식으로 정렬하면 원소의 뒤에 있는 원소에 포함되는지만 비교하면 되므로 N*log N으로 해결할 수 있더라.. 이 생각을 못했다.
반응형
'Computer science > Algorithm' 카테고리의 다른 글
[프로그래머스] Python3 - 기능개발 (1) | 2023.11.15 |
---|---|
[프로그래머스] Python3 - 의상 (0) | 2023.11.14 |
[프로그래머스] Python3 - H Index (0) | 2023.11.10 |
[프로그래머스] Python3 가장 큰 수 (0) | 2023.11.09 |
[프로그래머스] 호텔 대실 - Python3 (0) | 2023.07.12 |