[Programmers] 해시 : 전화번호 목록 (Python)

1일 1문제 18일차!

오늘의 문제는 프로그래머스의 전화번호 목록입니다.

 

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

첫번째 시도

먼저 그냥 이중 for문을 활용하여 코드를 짜 보았습니다.

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

결과는!

정확성은 만족하였으나

효율성에서는 시간초과로 실패하는 결과를 얻었습니다.

 

두번째 시도

이번에는 길이가 짧은 단어가 앞으로 오도록하여 이중 for문과 find명령어를 두번 사용하지 않아도 되도록 수정해보았습니다.

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

결과는!

세번째 시도 ( 2021년 3월 23일 댓글 보고 다시 푼 방법 )

어떤 분께서 댓글로 접두사가 아니라 중간에 겹치는 것 까지 False로 나온다는 댓글을 보고 다시 풀어보았습니다.

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
            break
    
    return answer

이번에는 가장 짧은 문자열부터 앞으로 나오도록 정렬하는 것도 같고

반복문도 같지만 그 안에 조건을 변경해보았습니다.

기존에는 앞쪽의 짧은 문자열이 뒤쪽의 긴 문자열에 포함되는지 여부를 체크하였는데 

댓글을 남겨주신 분 말씀처럼 중간에 겹치는 부분까지 False로 체크되는 문제가 있어서

슬라이싱을 활용하여 앞의 문자열의 길이만큼 앞에서부터 잘라와서 앞의 문자열과 같을 경우에 False로 정답이 나오도록 하였습니다.

댓글 남겨주셔서 감사합니다~

SOMJANG/CODINGTEST_PRACTICE