프로그래머스 코딩테스트 고득점 Kit_해시_전화번호 목록

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

인자로 주어진 전화번호 배열을 .sort()정렬하면 접두사인 관계끼리 붙어 있게 된다.
(전화번호는 int가 아닌 string으로 주어지기 때문에 정렬하게 된다면 '123'과 '1234'가 붙어있음)

따라서 주어진 전화번호 배열을 sort()로 정렬해 재배치 하고,
앞, 뒤 에 있는 번호끼리 길이를 비교하여 뒤에 있는 번호의 길이가 더 길 경우,
앞 번호 길이만큼 뒤 번호를 앞에서부터 자른 뒤, 비교하여 접두사인지 아닌지 판별한다.

구현 코드👇

def solution(phone_book):

    N = len(phone_book) #전화번호 개수
    phone_book.sort() #정렬하면 접두사인 관계끼리 붙어있게 된다.

    for i in range(N-1):
        n = len(phone_book[i])
        if len(phone_book[i+1]) > n and phone_book[i+1][:n] == phone_book[i]:
            return False

    return True

해시를 사용하여 구현한 코드👇

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

다음 아래의 코드는 위와 같은 방법이지만, 아래는 효율성 테스트3,4번을 통과하지 못한다.
(내가 생각하기에 해시에 in을 사용하는 것과 리스트에 in을 사용하는데 시간복잡도가 다르기 때문인거 같은데 해당 부분만 따로 포스팅을 해야겠다.)

def solution(phone_book):
    
    for phone_num in phone_book:
        temp = ''
        for num in phone_num:
            temp += num
            if temp in phone_book and temp != phone_num:
                return False
    
    return True

📝 초기 아이디어는 정렬하지 않고 모든 단어를 비교하는 바보 같은 방법을 생각했었다.🤨

두번째 아이디어로는 주어진 전화번호 배열을 for문으로 돌며 len_dict = {길이: [해당 길이에 해당하는 전화번호, ... ], ... }을 구했다.
구한 len_dict의 key와 주어진 전화번호 배열을 for문으로 돌며 전화번호의 길이가 len_dict의 key보다 클 경우 그만큼 잘라서 len_dict[key]에 존재하는지 확인하여 존재한다면 return False 했다. 해당 방법은 너무 복잡하게 생각한 탓에 효율성 테스트4에서 시간초과로 실패했다. 해시를 사용하게 간단하게 구현한 방법은 위의 코드이다.

문제의 답을 맞추는것도 중요하지만, 시간복잡도를 고려하며 단시간에 모든 테스트를 만족할 수 있는 프로그램을 짜는 방법을 더 익혀야겠다.

그 외에도 다양한 풀이가 있었는데, i와 i+1을 비교하는 방법 중 새로운 방법을 발견했다. 👇 참고해서 다음에 써먹어봐야지😆😆

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True