전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제
phone_book return
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false

입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

문제풀이

첫 번째 코드

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

전화번호부 리스트를 이중포문으로 돌려서 다 탐색하긔 ,,

보통은 1,2,3,4가 있다고 하면 1,2와 2,1은 같은 것으로 취급해서 한 번만 탐색하도록 하지만 여기서는 1에 접두어가 2가 되는 거랑 2에 접두어가 1이 되는 거랑 다른 문제이기 때문에 정말 모든 경우를 다 탐색해야 한다.

그래서 이중포문 플러스 if문까지 나오게 됐다는 슬픈 얘기..

if문을 나랑 나를 비교하면 안 돼서 넣어줬어요

저기 phone_book[i] == phone_book[j][:len(phone_book[i])]는 1이 2의 접두어인지 판단하기 위해서 1의 길이만큼만 2를 비교하게 하였다. 

for문 이중으로 쓰는 순간 사실 시간초과를 직감했다. 그리고 결과는 역시..

시간초과

코드 결과는 정확하게 나오지만 시간초과,, 그래도 91.7점이면 나쁘지 않네 ㅋ 하고 우선은 넘겨버림~

스터디 하던 중 sort를 쓰면 시간을 아낄 수 있다는 것, 그리고 for문을 이중으로 쓰지 않을 수 있단 것을 깨달아버림.

고칠 수 있을 것만 같은 느낌을 갖고 스터디 끝나자마자 다시 풀어봄

 

두 번째 코드

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])]:
                answer = False
                return answer
    return answer

sort쓰니까 옆에 애랑만 비교하면 되고 2가 1의 접두어일 때 정렬로 인해서 1,2로 정렬되기 때문에 2,1 순서는 탐색하지 않아도 된다.

따라서 이렇게 간결해졌고

통과!

sort사용해서 시간초과 해결하고 통과~!