[프로그래머스] Level2_전화번호 목록(해시)

📌문제 유형

해시

 

📌문제

프로그래머스

 

📌문제 풀이

1차 시도(정확성 : 54.2, 효율성 : 8.3, 합계 : 62.5)

def solution(phone_book):
    phone_dict = {i: phone_book[i] for i in range(len(phone_book))}
    
    for i in phone_dict.keys():
        for j in range(i+1,len(phone_dict)):
            if phone_dict[i] in phone_dict[j]:
                return False
    return True

2차 시도(정확성 :62.5, 효율성 : 4.2, 합계 66.7)

def solution(phone_book):
    phone_dict = {i: phone_book[i] for i in range(len(phone_book))}
    
    for i in phone_dict.keys():
        for j in range(i+1,len(phone_dict)):
            if phone_dict[j].startswith(phone_dict[i]) == True:
                return False
        return True

3차 시도(정확성 : 75, 효율성 : 12.5, 합계 87.5)

def solution(phone_book):
    phone_book = list(map(int, phone_book))
    phone_book.sort()
    phone_book = list(map(str, phone_book))
    
    phone_dict = {i: phone_book[i] for i in range(len(phone_book))}
    
    for i in phone_dict.keys():
        for j in range(i+1,len(phone_dict)):
            if phone_dict[j].startswith(phone_dict[i]) == True:
                return False
        return True

4차 시도(통과)

 - '문자'일 때 정렬 기준 적용

• 기본 sort일 때, 길이 상관없이 앞자리 숫자가 작은 순서대로 정렬

 - (for문 2번 사용할 경우 시간초과) for문 1번만 이용하여 이전 값과 다음값만 비교하기

• 값 중 앞에만 일치하는지 확인(startswith)

Python 문자열 비교 완전 일치 부분 일치 소스 예제

def solution(phone_book):
	# 문자열 정렬
    phone_book.sort()
    
    # (시간초과 피하기 위해) 이전 값과 다음 값만 비교
    for i in range(len(phone_book)):
        if i != len(phone_book) - 1:
            if phone_book[i+1].startswith(phone_book[i]) == True:
                return False
        else:
            break
    return True

 

📌다른 사람들의 풀이

zip 이용

 - zip으로 현재 값과 다음 값을 비교

def solution(phoneBook):
    phoneBook = sorted(phoneBook)
    
    # zip으로 현재 값, 다음 값만 비교 가능
    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

Hash 이용

def solution(phone_book):
    answer = True
    hash_map = {}
    
    # hash_map에 phone_book value 1로 해서 모두 저장
    for phone_number in phone_book:
        hash_map[phone_number] = 1
     
    # 번호 하나씩 탐색
    for phone_number in phone_book:
        temp = ""
        # 번호 다 쪼개기
        for number in phone_number:
            # temp에 넣어서 hash_map과 비교(단, phone_number와 다른 경우)
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

 

📌리뷰

- 정렬의 기본 개념

• '숫자'일 때 정렬 기준 : 숫자 작은 것부터 정렬
• '문자'일 때 정렬 기준 : 길이 상관없이, 숫자 작은 것부터 정렬

 

📌참고

[python] List to Dict (리스트를 딕셔너리로 변환) 총 정리!!

 

[Python] Dictionary 예제 - Keys(), Values(), items()

 

리스트의 문자열을 int 형태로 변환

 

[파이썬기초] 리스트 요소 길이 순으로 정렬