반응형
일단 문제는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3
첫 시도 방법
1. phone_book을 숫자 길이순으로 정렬
["12", "123", "456", "5678"]
2. 맨 처음 원소가 나머지 원소의 접두어인지 비교. 비교가 끝나면 다음 원소를 기준으로 비교.
Code
def solution(phone_book):
# 방법 1
# 낮은 길이의 숫자부터 정렬
phone_book.sort(key=len)
for i in range(len(phone_book)):
for j in range(i+1, len(phone_book)):
if phone_book[j].startswith(phone_book[i]):
return False
answer = True
return answer
이렇게 하면 정확도 테스트는 100% 통과하나 효율성 테스트에서 '시간 초과'로 실패한다.
두번째 시도 방법
대체 어떻게 하면 이 문제를 풀 수 있을까? 고민하다가 결국 다른 사람의 풀이를 봤다.
정렬을 굳이 문자열 길이순으로 할필요는 없고 사전순으로 정렬한후 비교해도 풀리는 문제다.
1. 문자열을 사전순으로 정렬
2. 이전 문자열이 다음문자열로 시작되는지 검사
def solution(phone_book):
# 방법 2
# 사전식으로 분류
# 12 13 2 24 3 3444 6
phone_book.sort()
for k in range(len(phone_book)-1):
if phone_book[k+1].startswith(phone_book[k]):
return False
answer = True
return answer
이 문제는 해시를 통해서 풀수도 있다고 하는데, 굳이 해쉬를 쓸 필요는 없을것 같다.
반응형
'ETC' 카테고리의 다른 글
[SQL] where에서 '같다' 또는 '같지 않다'를 검색하는 방법 (0) | 2022.01.15 |
---|---|
[SQL] 컬럼 내용에서 문자열 치환하기 (replace) (0) | 2021.10.12 |
[kubernetes] kubectl label selector에 여러개 라벨 조건 주기 (and 또는 or 조건) (0) | 2021.06.14 |
[kubernetes] 배포 방법 정리 (고정/롤링/블루-그린/카나리 릴리즈 배포) (0) | 2021.04.25 |
[kubernetes] resources의 limit과 request의 의미와 파드 우선순위 (0) | 2021.04.25 |