프로그래머스 전화번호 목록(Python)

https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3#

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

이번 문제는 다른 사람의 답을 보지 않고 풀어낸 문제였다. (역시 2 레벨 문제라 그런가..?)

그래도 마냥 쉽지만은 않았다. '접두어'라는 키워드를 잊어버린 채 풀이에 몰두했기 때문에 생각보다 시간이 좀 걸렸다.

해시 문제로 분류되었지만 정작 풀이에서는 해시를 쓰지 않고 풀었다.

첫 번째 시도

입력에 대해 정렬 시키는 것이 풀이의 핵심이라 해도 과언이 아니었다. 정렬만 시키면 생각은 매우 간단해지기 때문이다.

>>> mylist = ["123", "11", "678"]
>>> mylist.sort()
>>> mylist
["11", "123", "678"]

위와 같이 문자열에 대해 정렬을 시키면 바로 다음 인덱스의 값과 비교하기만 하면 된다.

이 아이디어로 구현한 코드는 아래와 같다.

def solution(phone_book):
    answer = True
    phone_book.sort()
    for n in range(len(phone_book) - 1):
        if phone_book[n] in phone_book[n + 1]:
            answer = False
            break
    return answer

이 코드로 실행을 해서 한 문제를 틀렸다.. 여기서 살짝 멘붕이 왔다.

틀렸던 원인에 대하여..

'접두어'라는 건 어떤 단어의 앞에 붙는 말이다. 그러니 코드에서도 앞에 붙는지에 대해 검사를 해야 한다.

하지만 in을 사용해 검사를 하면 중간에 포함되는 것까지 다 잡아버린다.

>>> "12" in "123"
True
>>> "12" in "312"
True

그래서 in 이 아닌 다른 방법을 사용해 검사를 해야 한다.

두 번째 시도

python 문자열에서는 'startswith' 함수를 제공한다.

https://docs.python.org/ko/3.8/library/stdtypes.html#text-sequence-type-str

str.startswith(prefix[, start[, end]])
문자열이 지정된 prefix 로 시작하면 True 를 돌려주고, 그렇지 않으면 False 를 돌려줍니다. prefix 는 찾고자 하는 접두사들의 튜플이 될 수도 있습니다. 선택적 start 가 제공되면 그 위치에서 검사를 시작합니다. 선택적 end 를 사용하면 해당 위치에서 비교를 중단합니다.

이 함수를 사용하면 앞에 붙는지에 대해서만 검사가 가능하다!

그래서 in을 startswith로 바꿔 구현한 코드는 아래와 같다.

def solution(phone_book):
    answer = True
    phone_book.sort()
    for n in range(len(phone_book) - 1):
        if phone_book[n + 1].startswith(phone_book[n]):
            answer = False
            break
    return answer

효율성 테스트에서 최대 90.54ms, 30.6MB 만큼의 자원을 소모했다.

 

문제를 꼼꼼하게 읽고 생각을 천천히 해보는 습관을 길러야 할 것 같다.