프로그래머스 코딩테스트 연습 Level 2 - 전화번호 목록 (Python)

프로그래머스 코딩테스트 연습 Level 2 - 전화번호 목록 (Python)

 

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중 해시(Hash) 관련 문제인,

[전화번호 목록] 문제를 Pythoon를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

• 구조대 : 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입니다.

 

 

작성한 답

solution.py

시간 초과로 실패한 코드

def solution(phone_book):
    for s in phone_book:
        for s_ in phone_book:
            if s != s_ and s_.startswith(s):
                return False
    return True

 

성공한 코드

def solution(phone_book):
    phone_book.sort()
    for s1, s2 in zip(phone_book, phone_book[1:]):
        if s2.startswith(s1):
            return False
    return True

 

설명

시간 초과로 실패한 코드는 해당 방식으로 하면 당연히 효율성 테스트에서 실패할 것이다 생각되는 코드로 예시를 보여드리기 위해 추가하였습니다.

직관적으로 생각했을 때 모든 번호를 반복하며 각자 전부 비교하는 것으로 문제를 해결할 수 있겠지만 해당 방식은 phone_book의 배열이 크고 앞부분에서 False 인 것을 판단하지 못했을 때 엄청난 시간이 걸릴 것입니다.

 

성공한 코드를 설명드리자면,

먼저 phone_book 배열에 sort() 를 사용하여 기본적으로 정렬하는 사전순 정렬로 정렬해줍니다.

이렇게 되면 만약 ["123", "567", "67", "354", "6789"] 라는 배열이 있을 때, ["123", "354", "567", "67", "6789"] 로 사전순 정렬이 됩니다.

정렬된 배열을 보면 바로 알 수 있듯이 사전순으로 정렬이 되면서 문제에서 원하는 다른 번호의 접두어가 되는 번호는 해당 번호의 바로 앞자리에 올 수 밖에 없게 됩니다.

그러므로 실패하는 코드와 달리 단 한번의 반복문을 사용하여 바로 뒤에있는 문자열의 시작으로 존재하는지만 판단하여 간단하게 문제를 해결할 수 있습니다.

 

for 문을 사용할 때 index를 사용할 수도 있겠지만 저같은 경우 zip을 사용하여 문제를 해결해 보았습니다.

phone_book이 ["123", "567", "67", "354", "6789"] 와 같다고 했을 때 위와 같은 방식으로 zip을 사용하면,

[('123', '354'), ('354', '567'), ('567', '67'), ('67', '6789')] 배열로 만들어지기에 반복문을 돌면서 배열의 바로 앞과 뒤를 비교하기가 수월해집니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.