문제
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
문제 해결 과정
사실 해시 문제라서 딕셔너리를 이용하려고 했지만 처음에 파이썬으로 해결하려 했을 때 정답이 보이질 않아 딕셔너리를 사용하는건 좀 포기했다.
일단 phone_book의 길이가 최대 100만이기 때문에 이중 포문을 이용하는 건 당연히 안된다고 생각했다.
일단 처음에는 이중 포문이든, 삼중 포문이든 시작해보고 해결하는 타입이라 그렇게 문제를 해결하려고 노력했다.
당연히 시간 초과 부분에서 문제가 생겼고, 그 다음에 해결해야 했지만 해결하지 못했다.
그러다가 블로그를 하나 참고했는데, 그 블로그에서도 딕셔너리를 이용하지 않고 슬라이싱과 스트링 메소드를 이용해서 풀었다.
일단 내가 알아차리지 못한 부분은 문자열 기준으로 정렬을 하면 이중 포문으로 phone_book을 돌아다닐(?) 필요가 없다는 것이다.
정렬을 하면 일단 문제 해결이 조금 수월해진다.
일단 슬라이싱을 이용해서 해결하는 방법은 다음과 같다.
i번 째 값이 있을 때 i+1과 비교를 하는데, i번째 값 만큼 i+1 값을 슬라이싱해서 같으면 무조건 False를 반환한다.
메소드를 이용하는 방법은 startswith라는 메소드를 이용하는 것인데, 저번에도 본 것 같지만 생각이 나지 않았다.
이것도 그냥 i+1번째.startswith(i번째)가 True이면 False를 반환한다.
자바스크립트에서도 startsWith 메소드가 있었다.
파이썬이랑 다른 점은 그냥 w가 소문자이고 대문자인 것이 달랐다.
최종 코드(Python)
# startswith 함수 사용
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i+1].startswith(phone_book[i]) :
return False
return True
# 슬라이싱 사용
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
return False
return True최종 코드(JavaScript)
function solution(phone_book) {
phone_book.sort();
for (let i = 0; i < phone_book.length - 1; i++) {
if (phone_book[i + 1].startsWith(phone_book[i])) {
return false;
}
}
return true;
}
새로 알게 된 점
Python, JavaScript
startswith 함수
(JS에서는 startsWith)
참고 블로그
