[프로그래머스 Lv.2] 전화번호 목록 (Python)

문제

 

입출력 예제

 

이 문제를 보고 일단은 정렬을 해야 비교를 하기 수월할 것이라는 생각이 들었습니다.

정렬을 하면 번호의 길이 순 & 크기 순으로 정렬이 된다고 생각하여 길이가 더 큰 것은 접두어가 될 수 없기 때문에 순서대로 뒤에 있는 모든 번호들과 비교하여 접두어인지 판별하려고 하였습니다.

 

첫 코드

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if phone_book[i] == phone_book[j][:len(phone_book[i])]:
                answer = False
                return answer
            
    answer = True
    return answer

첫 코드에서는 for문 두 개를 이용하여 폰 번호가 자신의 뒷 index에 위치한 모든 폰 번호와 비교하여 접두어가 있는지 판별하였습니다.

하지만 이 코드는 시간 초과로 효율성 테스트 3, 4번에서 실패가 떴습니다.

다른 사람들의 문제 풀이를 보니 for 문이 중첩되어 시간이 초과되는 것 같았습니다.

그리고 대부분의 사람들이 zip, startswith를 사용한 것을 확인하였습니다.

 

zip과 startswith이 무엇인지 검색해 보았는데

 

zip

zip은 두 리스트를 매칭해줄 때 사용합니다.

list1 = ['one', 'two', 'three']
list2 = ['1', '2', '3']

for x, y in zip(list1, list2):
	print(x, y)

위와 같이 zip을 사용하는 경우가 많은데 위의 코드를 실행할 경우, 결과는 one 1, two 2, three 3으로 출력이 된다.

 

만약 두 list의 길이가 다를 경우 더 짧은 list를 기준으로 다른 list가 잘린다고 한다.

 

startswith

startswith은 문자열이 특정 문자열로 시작하는지 확인할때 사용한다.

str = "abcd"

ans = str.startswith("ab") -> True
ans = str.startswith("dc") -> False

 

이 두 함수를 사용하는 것을 알게 되어도 어떻게 코드를 작성하는지 알 수 없었다. 왜냐하면 폰 번호를 자기보다 길이가 긴 나머지 모든 폰번호와 비교를 해야한다고 생각했기 때문이다.

 

그렇지만 주어진 phone_book의 요소들은 모두 문자열이기 때문에, 정렬을 하면 문자열의 앞 index부터 비교하여 숫자가 작은것부터 정렬이 된다. 즉, 숫자 & 길이 순으로 정렬이 된다. 숫자 요소의 list 정렬과는 정렬 결과가 달랐던 것이다. 그렇기 때문에 정렬후에 바로 뒷 폰번호와만 비교를 하여 접두어인지 확인하면 되는 것이었다.

최종 코드

def solution(phone_book):
    phone_book.sort()
    for i, j in zip(phone_book, phone_book[1:]):
        if j.startswith(i) :
            answer = False
            return answer
            
    answer = True
    return answer

1. phone_book을 정렬해준다.

2. zip을 이용하여 모든 번호를 바로 뒷 index의 번호와 매칭해준다.

3. startswith 함수를 이용해 해당 번호가 뒷 번호의 접두어인지 확인해준다.

4. 접두어가 맞을 경우 False를 리턴해준다.

5. 모든 번호를 탐색했지만 접두어가 없는 경우 True를 리턴해준다.

 

다른 사람의 풀어

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

hash_map : key 값 = phone_number, value 값 = 1

첫번째 for문에서는 phone_book에 있는 모든 phone_number값을 돌린다. 내부 for문에서는 해당 phone_num 문자열 안에있는 문자를 순서대로 돌린다. temp에 for문이 돌때마다 숫자를 추가해주는데, temp값이 hash_map 딕셔너리의 key 값으로 있는 경우 접두어가 있는 것이므로 False 값을 리턴해준다.