✔Algorithm/programmers/해시/level2/전화번호 목록 (with python)
9766 단어 알고리즘 문제programmers해시programmers
📖 문제
📝 풀이 과정
- 리스트 phone_book을 정렬한다.
왜냐하면 앞글자들이 같아야지만 접두어가 될 가능성이 높은데, 정렬을 해야 앞글자가 비슷한 것끼리 모인다.
- 새로운 딕셔너리에 값을 넣는다.
key는 전화번호의 첫 숫자를, value에는 key를 첫 숫자로 가지는 전화번호 리스트를 담는다.
- 딕셔너리 예시)
- data의 key별로 values를 순회한다.
순회하면서 앞에 있는 수가 뒤에 있는 수들의 접두어가 될 수 있는지 확인한다.
-> 이게 가능한 이유는 리스트 phone_book이 정렬되어 있어서 딕셔너리 data의 values에 들어가는 값들도 정렬되어있음을 보장하기 때문이다.
왜냐하면 앞글자들이 같아야지만 접두어가 될 가능성이 높은데, 정렬을 해야 앞글자가 비슷한 것끼리 모인다.
key는 전화번호의 첫 숫자를, value에는 key를 첫 숫자로 가지는 전화번호 리스트를 담는다.
- 딕셔너리 예시)
순회하면서 앞에 있는 수가 뒤에 있는 수들의 접두어가 될 수 있는지 확인한다.
-> 이게 가능한 이유는 리스트 phone_book이 정렬되어 있어서 딕셔너리 data의 values에 들어가는 값들도 정렬되어있음을 보장하기 때문이다.
그리고 코드는 좀 지저분해지지만.. answer가 False임에도 불구하고 남은 for문을 다 돌아가는 것을 방지하기 위해서
if answer == False :
break
을 좀 남발했다.... 이렇게 해도 효율성 테스트 3번과 4번은 통과하지 않았지만 이 코드마저 없었다면 효율성 테스트 1번과 2번도 통과하지 못하는 것을 확인했다.
⌨ 코드(틀린 코드)
-> 정확성 테스트는 모두 통과했지만, 효율성 테스트3,4는 통과하지 못한 코드입니다.
def solution(phone_book):
answer = True
data = dict()
# 1. 리스트 phone_book을 정렬한다.
phone_book.sort()
# 2. 새로운 딕셔너리에 값을 넣는다.
for phone_number in phone_book:
# 이미 딕셔너리에 첫글자가 있다면
if phone_number[0] in data:
data[phone_number[0]].append(phone_number)
else:
data[phone_number[0]] = [phone_number]
# 3. data의 key별로 values를 순회한다.
for num in data:
if answer == False:
break
p_numbers = data[num]
# 앞쪽에 있는 수 -> index i
for i in range(0,len(p_numbers) - 1):
if answer == False:
break
# 뒤쪽에 있는 수 -> index j
for j in range(i + 1, len(p_numbers)):
if p_numbers[i] in p_numbers[j]:
answer = False
break
return answer
⌨ 다른 분의 코드 참고 -> 더 효율적인 코드
- phone_book을 정렬한다면 어떤 번호의 접두어가 될 수 있는 코드는 서로 인접하게 된다. 따라서 앞뒤 번호끼리만 비교해주면 정답을 구할 수 있다.
- 하지만 해시 자료형은 쓰지 않는다.
def solution(phone_book):
answer = True
phone_book.sort()
for i in range(len(phone_book) - 1):
l = len(phone_book[i])
if phone_book[i] == phone_book[i + 1][:l]:
answer = False
return answer
⌨ 다른 분의 코드 -> 해시맵을 사용한 코드
- 해시맵에 phone_book에 있는 전화번호를 모두 key값으로 저장한다. 이때 value는 의미없는 값이다.
- phone_book에 있는 전화번호를 한글자씩 가져와 temp 변수에 붙여가면서 현재까지 구한 temp가 해시맵에 존재하는지 검사한다.
def solution(phone_book):
answer = True
hash_map = {}
# 해시맵에 phone_book에 있는 전화번호를 모두 key값으로 저장한다.
for phone_number in phone_book:
hash_map[phone_number] = 1
# phone_book에 있는 전화번호를
for phone_number in phone_book:
temp = ""
# 한글자씩 가져와
for number in phone_number:
# temp 변수에 붙여가면서
temp += number
# 현재까지 구한 temp가 해시맵에 존재하는지 검사한다.
if temp in hash_map and temp != phone_number:
answer = False
return answer
Author And Source
이 문제에 관하여(✔Algorithm/programmers/해시/level2/전화번호 목록 (with python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yellowsummer/Algorithmprogrammers해시level2전화번호-목록저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)