문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

풀이

아이디어

• 일단 어떤 전화번호가 다른 전화번호의 접두어가 되는 케이스를 "빨리" 찾으려면 phone_book 배열을 숫자로 오름차순으로 정렬하는 것이 아니라, 문자 그대로 오름차순 정렬을 해야 한다.
• 문자 그대로 오름차순 정렬을 했을 때, 어떤 전화번호가 다른 전화번호의 접두어가 되려면, 무조건 다른 전화번호보다 하나 앞에 있어야 한다. (즉, 정렬된 phone_book 배열을 돌면서 각각 각자 앞에 번호 하나만 검사했을 때, 접두어면 끝)
• 접두어를 판단하는 방법: String.prototype.indexOf()를 활용한다. 이때 indexOf에서 리턴받은 결과가 0이어야만 접두어이다.

코드

function solution(phone_book) {
    let answer = true;
    //일단 phone_book을 문자 순으로 오름차순 정렬
    phone_book.sort();
    
    phone_book.forEach((phone, idx) => {
        if(phone.indexOf(phone_book[idx - 1]) == 0) answer = false;
    })
    
    return answer;
}

🔆 접두어인지 판단하는 방법으로 나는 Stirng.prototype.indexOf()의 리턴값이 0이 될 때를 봤는데, 애초에 String.prototype.startsWith()라는 함수가 있었다! 이걸 쓰면 코드가 더 가독성이 좋아질 것 같다!

파이썬 코드

def solution(phone_book):
    #우선 phone_book을 정렬해준다.
    phone_book.sort()
    #그러면 앞에거가 무조건 바로뒤에거의 접두어여야만 true
    for i in range(len(phone_book) - 1):
        if phone_book[i] in phone_book[i+1] and phone_book[i][0] == phone_book[i+1][0]:
            return False

    return True

def solution(phone_book):
	phone_book.sort()
    for phone1, phone2 in zip(phone_book, phone_book[1:]):
    	if phone2.startswith(phone1):
			return False
    return True