프로그래머스 Lv.2 전화번호 목록

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

풀이

1번째 풀이

어떤 번호가 다른 번호의 접두어라면

어떤 번호의 문자열이 다른 번호의 문자열 안에 있다.

따라서 다음과 같이 코드를 작성했다.

def solution(phone_book):
    n = len(phone_book)
    for i in range(n):
        for j in range(n):
            if i != j:
                if phone_book[i] in phone_book[j]:
                    return False

    return True

그렇지만 정확성 테스트에서 100%가 아니었다.

왜일까?

위의 코드의 경우 

어떤 번호가 다른 번호의 접두어가 아니래도

어떤 번호의 문자열이 다른 번호의 문자열 안에 있는 것이 가능하다.

ex)

'119'

'00119'

 

 

두번째 풀이

어떤 번호가 다른 번호의 접두어라면

어떤 번호의 문자열이 다른 번호의 문자열 안에 있고

두 번호간의 첫 문자가 같다.

따라서 다음과 같이 코드를 작성했다.

def solution(phone_book):
    n = len(phone_book)
    for i in range(n):
        for j in range(n):
            if i != j:
                if phone_book[i] in phone_book[j] and phone_book[i][0] == phone_book[j][0]:
                    return False

    return True

아까보다는 정답률이 올라갔지만 그렇지만 여전히 정확성 테스트에서 100%가 아니었다.

왜일까?

위의 코드의 경우 다음과 같은 예외가 발생한다.

 

 

ex)

'119'

'10119'

 

세번째 풀이

 

어떤 번호가 다른 번호의 접두어라면

두 번호간의 첫 문자가 같고 

'어떤 번호' = '다른 번호'[0: 어떤 번호의 전체 길이]

가 성립해야 한다.

 

여기서 sort를 하여 올림차순으로 정렬했다.

이 때는 두번째 번호가 첫번째 번호의 접두어가 되는 경우를 배제하고

첫번째 번호가 두번째 번호의 접두어가 되는 경우만 카운트하면 된다.

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

 

정확성 테스트는 100%이나 효율성 테스트에 문제가 생겼다.

이 코드를 더 빨리 실행하게 만들어야 했다.

 

 

최종 풀이

위의 풀이에서 

정렬된 상태에서는

바로 인접한 상태의 문자열들에서만 

어떤 번호가 다른 번호의 접두어인 경우가 발생한다는 것을 깨달았다.

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