[프로그래머스] 42577. 전화번호 목록

Programmers - 42577. 전화번호 목록

접근1

해시? 딕셔너리로 접근? set으로 접근?

고민 많이 했음.

2중 for문으로 처리하면 쉽겠지만, 당연히 시간초과 뜰 거고...

 

모든 phone_num의 원소마다

"1234"라면 1 12 123 1234 이렇게 모든 경우의 수를 따져서

그 숫자가 (자신 제외) phone_num에 있는지 조사 -> 성립.

대신, 이제 찾을 때 set에 넣어서 하면 될 듯?

def solution(phone_book):
    set_book = set(phone_book)

    for phone in phone_book:
        number = ""
        for num in phone:
            number += num
            if number in set_book and number != phone:
                return False
    return True

성공.

잠깐 빼먹었던 것은, 자신 제외로 조사해야 했던 것.

 

다른 풀이

어... 정렬하면 사전순으로 정렬돼서 양 옆만 조사하면 된다고 한다..

너무 편하게 푸는 것 아니냐고 ㅋㅋ

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True