프로그래머스_해시_전화번호 목록

난이도가 낮은편인 문제

해시를 이용하지 않고 풀었다.

 

다만, 효율성 테스트에서 처음에 떨어졌음.

 

 

문제

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 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

 

---

첫번째 코드

 

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

 코드를 이렇게 쓰면 결국 answer은 이미 False인데도 return이 되지않고 2중 포문이 처음부터 끝까지 다돌아 가게된다.

즉, 매우 비효율적

 

두번째 코드

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

 어차피 만약 하나라고 접두어로 시작한다면 결과는 False이므로 for문에서 만나자마자 return을 해주자.

그리고 for문이 다 돌아도 True라면 그때 True를 반환해주면된다.

 

다른 방법들

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

제일 처음에 풀었을때인데 startswith라는 attribute가 생각나지 않아 슬라이싱을 이용해서 다소 코드가 난해해 보이는 면이 있긴하다.

근데 for문을 하나밖에 안썼었다. 오히려 시간이 빠른가 확인해보자

 

 

오늘 쓴 코드

 

옛날에 쓴 코드

놀랍게도 옛날에 쓴 코드가 더 빠르다.

그때는 효율성을 고려도 안하고 풀었을텐데..

 

사실 이 문제에서 시간차가 나는 이유는

sorting했을때는 바로 옆에 글자만 확인해주면 된다는 것에 있다.

즉 i로 접두사를 검사할 때 i+1 ~ 끝 까지 해줄 것이아니라

i와 i+1만 비교해도된다 왜? sorting했잖으니까.

 

 

실전에서는 복잡한 코드를 먼저 짜놓고, 시간효율성을 나중에 따지는 형식으로 문제를 잘 풀 수 있기를 바란다.