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

그렇게 어렵지 않았던 문제이고, 나는 배열을 활용해서 풀었다. 그런데, 시간초과랑 테스트 케이스에서 2~3개 정도 틀렸다.

풀이 이전에, 알고넘어가야 할 메소드만 정리한다.
문자열 클래스에서 제공되는 메소드!

• isdigit() -> 해당 문자열이 숫자인가?
• stasrtswith(a) -> a로 시작하는 문자열인가?
• swapcase() -> 문자열의 대소문자를 바꿔준다.
  훨씬 더 많은데, 일단 이것만 기억하기로...

1. 리스트로 풀이

일단 이 문제를 해시를 사용해서 풀기에는 애매했다.
분명 내가 해시를 잘 활용할 줄 몰라서 그렇다.

일단 내가 처음 풀었던 풀이는 다음과 같다.

def solution(phone_book):
    for idx, val in enumerate(phone_book):
        temp = phone_book.copy()
        del temp[idx]
        for i in temp:
            if val in i:
                return False
    else:
        return True

그리고, 점수는 75점이 나왔다. 일부 테스트 케이스에 틀린 것이 있어서 자세히 살펴보니 접두사 라고 했다. 그러니까 문자열 앞부분에 다른문자와 정확히 매치되는지 확인해봐야 한다. 그래서 정규표현식으로 바꿔서 다시 풀이했다.

 

import re

def solution(phone_book):
    for idx, val in enumerate(phone_book): #O(n)
        for i in phone_book:
            if i != val:
                find_pattern = re.search(f"^{val}",i)
                if find_pattern:
                    return False
    else:
        return True

이렇게 하면 시간초과가 나온다. 흠...

2. 다른 풀이

블로그를 보면서 다른 풀이를 살펴봤다. 내가 놓쳤던 포인트는 정렬을 안해서 그렇다. 왜 정렬할 생각을 못했지..?
하나의 원소를 제외한 나머지 원소와 비교를 하려면, 루프를 한번 더 돌아야 한다고 생각했다. 그런데, 정렬을 해버리면 어차피 이전의 원소들은 더 작기때문에 이전에 같은 패턴이 이미 나와버렸거나 아닌 경우밖에 없다.

import re

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

3. 해시로 풀이

앞선 배열을 활용한 문제는 비교 대상문자열을 앞에서부터 길이만큼 잘랐을때 같은지를 확인했다. 해시로 풀게되어도 비슷한 맥락인데, 조금 다르다. 근데 굳이 해시로 풀 필요는 없을것 같다..

 

def solution(phone_book):
    answer = True
    dic ={} #key,value형태의 딕셔너리이용
    for pNumber in phone_book:
        dic[pNumber] = 1 #key:폰번호 value:1
    for pNumber in phone_book: #각각 폰번호마다 검사
        temp=""
        for num in pNumber: #폰번호를 한글자로 쪼개서 반복문 "243"이면 "2" "4" "3"
            temp +=num #쪼갠 숫자를 반복문이 돌아갈 때마다 붙음  
            if temp in dic and temp!=pNumber: #딕셔녀리의 키로 존재하는지 검사
                answer = False
    return answer