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

/ 1 번째 제출 /

 

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

 

정확성: 83.3 (테스트 20 / 20)

효율성: 8.3 (테스트 2 / 4) : 사유는 시간초과

합계: 91.7 / 100.0

 

시간초과가 나올 것을 어느정도 예상하고 우선 정확성 테스트를 위해 한 번 제출해봤습니다.

역시나 시간 초과가 뜨고 의외로 테스트케이스 2개까지도 오케이난 것에 생각보다는 빨랐구나 싶었지만, 효율성이 100%가 아님에 반성하며 수정 요소를 생각했습니다.

 

---

/  2번째 제출  /

 

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

 

채점 결과

 

정확성: 83.3

효율성: 16.7

합계: 100.0 / 100.0

 

의외로 금방 아이디어를 떠올렸습니다.

생각해보니 길이에 상관없이 접두어만 일치하면 되니까 숫자 그 자체를 기준으로 생각하는게 더 옳다는 생각이 들었습니다.

그리고 무엇보다 이렇게 하면 for문을 중첩하지 않고 한 번만 돌리면 되기 때문에 타임아웃이 날 염려가 적다고 생각했습니다. 그대로 구현했고, 기분 좋게 맞아떨어졌습니다.
배열이니까 인덱스 범위 항상 신경 쓰며 range작성 하는 것도 다시 한 번 유념하기로 합시다.

---

 

[ 다른 사람 풀이 확인 ] 

 

1) 

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

 

동작 원리는 제 2째 풀이랑 같지만, 처음 보는 메서드 startswith()가 있어서 정리하고자 가져왔습니다.

이름에서 직관적으로 파악이 가능한 메서드다. 파라미터로 시작하냐 여부를 boolean값으로 돌려줍니다.

내부 구현사항과 관련해 성능에 관해서 궁금해하는 분들이 많으시고 저도 궁금해서 검색해봤습니다.

 

startswith() 설명: https://docs.python.org/3/library/stdtypes.html?highlight=startswith#str.startswith

 

설명1) https://leetcode.com/problems/find-and-replace-in-string/discuss/134758/Java-O(n)-solution

 

Java O(n) solution - LeetCode Discuss

 

( 더 참고할 것 ) 

 

in 과 startswith() 비교에 대한 글 : https://stackoverflow.com/questions/44520179/comparing-the-speed-of-startswith-vs-in

 

---

2)

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

 

리스트에 접근하는 것보다 딕셔너리 접근이 더 빨라 이렇게도 구현하고 싶었는데, 다른 분들은 이렇게 푸셨네요.

 

일단 풀이를 하자면, 

 

1. 전화번호부에 있는 모든 번호를 각각 딕셔너리에 저장합니다. (중복 없으므로 값은 1

2. 전화번호부에 있는 모든 번호를 돌며 

     2-1. 각 번호 개벌 숫자를 돌며 temp를 늘려나가고, temp가 적절히 커져서

            딕셔너리에서 그 값을 본인 값으로 갖는 키밸류값을 찾으면 접두어를 찾은 것으로 생각합니다.

            (물론 그 키밸류값이 자기 자신이 아니도록 and문으로 조건을 걸어줍니다.)

 

---

Memo. 아이디어는 간단하고 떠올리기도 쉽지만, 내가 딕셔너리를 자연스럽게 떠올리고 익숙하게 사용하지 않아서

해당 해시맵 유형을 보면서 계속 익혀야겠다.

 

모든 문제는 백지복습으로 각 풀이 외우도록 하자.