1. 전화번호 목록
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.
2. 문제 접근
-
전화번호: N개
-
한 전화번호가 다른 전화번호의 접두어인지 확인
-
아무 한 전화번호가 다른 전화번호의 시작 일부와 동일하면 false, 연관 없으면 true
-
해결책
- 2중 반복문을 통해 서로가 서로의 접두어인지 전부 확인
- 정렬 후, 1중 반복문을 통해 앞 번호가 뒷 번호의 접두어인지 확인
- 해시 이용하여 접두어가 존재하는지 확인
해결책 1번
-
모든 전화번호를 서로 비교
1) phone_book[i]가 phone_book[j]로 시작하는지, 반대로 phone_book[j]가 phone_book[i]로 시작하는지 양쪽을 다 확인
2) 둘 다 없으면 i, j의 index 값을 바꿔가며 전부 비교 -
String1.startswith(String2)
1) String1이 String2로 시작되는지 (String2가 String1의 접두어인지)를 찾아주는 기본 함수
def solution(phoneBook):
# 비교할 A 선택
for i in range(len(phoneBook)):
# 비교할 B 선택
for j in range(i+1, len(phoneBook)):
# 서로가 서로의 접두어인지 확인
if phoneBook[i].startswith(phoneBook[j]):
return False
if phoneBook[j].startswith(phoneBook[i]):
return False
return True해결책 2번
-
정렬
-
반복문
1) [0]의 값이 [2]의 값의 접두어인지 확인할 필요가 없어졌다- [0]이 [2]의 접두어였다면, [1]도 [2]의 접두어라는 것이 보장되기 때문이다
2) [1]의 값이 [0]의 접두어인지 확인할 필요가 없어졌다 (단방향)
- 정렬을 했기 때문에, [0]이 [1]의 접두어일 순 있어도, [1]이 [0]의 접두어일 수는 없다.
def solution(phoneBook):
# 정렬
phoneBook.sort()
# 전화번호부 2개씩 확인해서 접두어인지 확인
for i in range(len(phoneBook) - 1):
if phoneBook[i+1].startswith(phoneBook[i]):
return False
return True해결책 3번
-
HashMap 만들기
1) HashMap이란 Key-Value의 Pair를 관리하는 클래스
2) Key는 phone_number / Value는 1로 설정
3) Value == 1의 의미는 숫자가 1개 존재한다는 것이다 -
모든 전화번호 Hashing 하기 (Hash Map에 추가하기)
1) 'Hashing을 한다'라고도 표현하는데, HashMap에 전화번호를 전부 추가해보자. -
각 전화번호의 접두어가 HashMap에 존재하는지 확인하기
1) 존재하는 모든 전화번호가 HashMap에 등록
2) 각 전화번호의 접두어가 HashMap에 존재하는지 확인
(접두어를 추출해서 String이라는 Key가 현재 hash_map에 존재하는지 확인)
def solution(phoneBook):
hash_map = {}
# Hash map 생성
for phone_number in phoneBook:
hash_map[phone_number] = 1
# 접두어가 Hash map 에 존재하는지 확인
for phone_number in phoneBook:
judoo = ""
# 각 번호의 접두어 추출 ("1", "12", "123")
for number in phone_number:
judoo += number
# Hash map에 접두어 확인 (기존 번호와 같은 경우 제외)
if judoo in hash_map.keys() and judoo != phone_number:
return False
return True