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

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

코딩테스트 연습 - 전화번호 목록

2021.09.28 추가

 

친구랑 스터디 하다가 다시 이 문제를 풀어보았는데 1시간 걸림....

hidden case : ["934793", "34", "44", "9347"] false

def solution(phone_book):   
    sorted_book = sorted(phone_book)
    prifix = sorted_book[0]
        
    for i in range(1,len(sorted_book)):
        if len(sorted_book[i-1])<=len(sorted_book[i]): 
            prifix = sorted_book[i-1]
            if sorted_book[i-1][0:len(prifix)] == sorted_book[i][0:len(prifix)]: 
                return False
    return True

 

그래도 검색하지 않고 내 머리에서 나온 코드라 나름의 의미는 있는 듯 하다.

보니까 prifix를 선언하지 않고 그냥 앞뒤만 비교하면 되는 거 같아서

def solution(phone_book):   
    sorted_book = sorted(phone_book)
        
    for i in range(1,len(sorted_book)):
        if sorted_book[i][0:len(sorted_book[i-1])] == sorted_book[i-1] : 
            return False
    return True

 

최종 코드는 위와 같다.

---

해시 문제를 하나 더 풀어보고싶어서 바로 밑에 문제를 풀어보았다.

 

해시를 쓰라고 써있었지만 사실 왜 해시를 써야하는지 모르겠어서...

처음엔 해시를 쓰려고 했지만 생각할수록 그냥 배열로 해도 풀릴거같아서 다 지우고 다시 풀었다.

 

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

변수를 선언해서 접두사를 받아서

배열을 돌면서 문자열 slice후 각 전화번호 앞부분이 접두사와 동일한지 검사했다

이랬을때의 문제점은 아래 2가지로 테스트케이스도 다 통과 못했고 효율성 테스트도 통과 못했다.

 

1. 맨 앞에 있는게 꼭 접두사가 아닐 수 있다

  => index를 바꿔가면서 검사해야함

2. 다 돌아야해서 효율성에도 별로임

  => sort 함수로 배열하면 숫자 순서로 배열되어서 유무를 더 빨리 판단할 수 있다

 

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

위와 같이 수정했다. sort만 추가하면 됐었다.

---

TODO

왜 해시문제인지 고민해보기..

왜 해시인지는 알아냈다

다시 이 문제를 풀어봤는데 sort시 사전 순으로 정렬할거냐, 길이 순으로 정렬할거냐에 따라 달라진다.

하지만 사전순으로 정렬하는게 더 빠를거같기도 하고.. 그렇게 해서도 충분히 풀린다.