프로그래머스 - 전화번호 목록 (해시)

이번 포스팅에서는 프로그래머스의 전화번호 목록 (해시) 코딩테스트 연습 문제를 풀어봅니다.

문제 설명

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

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

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

제한 사항

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

입출력 예

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
"12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

문제 풀이

리스트의 각 요소에 대한 비교가 필요해 보입니다. 비교에 버블정렬 방식으로 비교를 수행 하였습니다.

a=[1,2,3,4,5]
for i in range(len(a)):
    for j in range(1+i, len(a)):
        print(a[i],':',a[j])

1 : 2
1 : 3
1 : 4
1 : 5
2 : 3
2 : 4
2 : 5
3 : 4
3 : 5
4 : 5

위의 비교 방식을 문제에 대입하면 아래와 같습니다.

def solution(phone_book):
    for i in range(len(phone_book)):
        for j in range(1 + i, len(phone_book)):
            print(phone_book[i], ':', phone_book[j])

solution(["119", "97674223", "1195524421"])

119 : 97674223
119 : 1195524421
97674223 : 1195524421

최종적으로 문자열 비교를 이용하여 앞의 문자열이 뒤의 문자열의 맨 앞에 포함되어 있을경우 False를 리턴하며 바로 루프를 종료하고, 포함된 문자열이 없을때는 True를 리턴합니다. 전화번호부를 정렬하여 앞의 전화번호가 항상 작은수가 되도록 합니다.

def solution(phone_book):
    phone_book = sorted(phone_book)
    bl = len(phone_book)
    for i in range(bl):
        for j in range(1 + i, bl):
            pl = len(phone_book[i])
            if phone_book[i] == phone_book[j][:pl]:
                return False
    return True

print(solution(["119", "97674223", "1195524421"]))
print(solution(["123","456","789"]))
print(solution(["12","123","1235","567","88"]))

False
True
False

결과는 정확도 테스트는 잘 통과 하지만…. 효율성 테스트에서 시간 초과가 뜹니다. ㅠㅠ

역시 버블 비교를 통한 방식은 효율성에 문제가 생기는거 같습니다. ㅠㅠ
그리고 생각해 보니 정렬을 할 경우 앞의 번호가 포함될 수 있는 경우의 수는[‘12’, ‘1223’]처럼 앞과 바로 뒤의 리스트 값이 해당 하는 경우 뿐 이였습니다. 정렬을 진행 할때 [“12”,”567”,”123”]의 경우 [“12”,”123”,”567”] 되기 때문입니다. 코드를 아래와 같이 수정해 주었습니다.

def solution(phone_book):
    phone_book = sorted(phone_book)
    for i in range(len(phone_book)-1):
        pl = len(phone_book[i])
        if phone_book[i] == phone_book[i+1][:pl]:
            return False
    return True

print(solution(["119", "97674223", "1195524421"]))
print(solution(["123","456","789"]))
print(solution(["12","123","1235","567","88"]))

False
True
False

결과를 다시 확인해 보니 루프가 많이 줄어서 효율성 테스트도 무사히 통과 되는 것을 확인 할 수 있습니다.