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

문제 : programmers.co.kr/learn/courses/30/lessons/42577

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

구조대 : 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

In [1]:

def solution(pb):
    answer = True
    for i in range(len(pb)):
        for j in range(len(pb)):
            if i == j:
                pass
            elif pb[i] == pb[j][:len(pb[i])]:
                return not answer
            else:
                return answer

In [2]:

pb = ["119", "97674223", "1195524421"]
# pb = ["12", "123", "1235", "567", "88"]'
# pb = 	["123", "456", "789"]

In [3]:

solution(pb)

Out[3]:

True

In [6]:

def solution2(pb):
    answer = True
    for i in range(len(pb)):
        for j in range(len(pb)):
            print(i,j)
            if i == j:
                print(f'{i}번째 {j}번째 is the same number')
                pass
            elif pb[i] == pb[j][:len(pb[i])]:
                print(f'pb[{i}], pb[{j}][:len(pb[{i}])] is the same, {len(pb[i])}')
                return not answer
            else:
                return answer
                pass

In [7]:

solution2(pb)

0 0
0번째 0번째 is the same number
0 1

Out[7]:

True

내가 의도한 것은 for문이 전체적으로 i,j 인덱스가 (0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) 순으로 돌아가면서 찾는 것이었는데 다 돌아가지도 않고 결과값이 이상하게 나왔었다. 이상해서 다시 for 문이 어떻게 돌아갔나 직접 프린트 해서 보니까 i,j가 0,1일 때까지만 돌아가고 True를 반환하고 그 이상으로는 안돌아갔다.

한참을 생각해보니까 elif 문에서 그냥 0번째 문자열 '119'에서 1번째 문자열에서 2번째까지인 '976'과 맞지 않다는 것까지만 확인하고 끝난 것 같았다. 그래서 while문을 넣어봤다.

In [9]:

def solution3(pb):
    answer = True
    while True:
        for i in range(len(pb)):
            for j in range(len(pb)):
                print(i,j)
                if i == j:
                    print(f'{i}번째 {j}번째 is the same number')
                    pass
                # elif pb[i] != pb[j][:len(pb[i])]:
                #     return True
                    
                elif pb[i] == pb[j][:len(pb[i])]:
                    print(f'pb[{i}], pb[{j}][:len(pb[{i}])] is the same, {len(pb[i])}')
                    return False
        break

In [10]:

solution3(pb)

0 0
0번째 0번째 is the same number
0 1
0 2
pb[0], pb[2][:len(pb[0])] is the same, 3

Out[10]:

False

제대로 나왔다. 다시 테스트 해보니 pb = ["123", "456", "789"] 에서 막힌다

In [11]:

 pb = ["123", "456", "789"]
solution3(pb)

0 0
0번째 0번째 is the same number
0 1
0 2
1 0
1 1
1번째 1번째 is the same number
1 2
2 0
2 1
2 2
2번째 2번째 is the same number

여기서 null값이라고 나왔다고 하던데 다시 코드를 고쳐보겠다.

In [21]:

def solution4(pb):
    answer = True
    while True:
        for i in range(len(pb)):
            for j in range(len(pb)):
                print(i,j)
                if i == j:
                    print(f'{i}번째 {j}번째 is the same number')
                    pass
                    
                elif pb[i] == pb[j][:len(pb[i])]:
                    print(f'pb[{i}], pb[{j}][:len(pb[{i}])] is the same, {len(pb[i])}')
                    return not answer
        return answer   # 여기 추가 : 모두 돌았을 때 아무것도 안나오면 True로 돌리기
        break

In [22]:

# pb = ["119", "97674223", "1195524421"]
# pb = ["12", "123", "1235", "567", "88"]
pb = ["123", "456", "789"]
solution4(pb)

0 0
0번째 0번째 is the same number
0 1
0 2
1 0
1 1
1번째 1번째 is the same number
1 2
2 0
2 1
2 2
2번째 2번째 is the same number

Out[22]:

True

for문만 돌리기 때문에 효율성에선 떨어질 수 있으나 다시 테스트 해보겠다. 역시나 시간초과로 문제가 틀렸다... ㅠㅠ

정확성: 83.3

효율성: 8.3

합계: 91.7 / 100.0

약간 찾아봤는데 sorted를 쓰는 경우가 있었다. 내가 왜 이걸 생각 못했을까?

In [91]:

def solution5(pb):
    answer = True
    # 접두어가 있으면 False
    pb = sorted(pb)
    print(pb)
    while True:
        for i in range(len(pb)):
            for j in range(i+1, len(pb)):
                print(i,j)
                if pb[i] == pb[j][:len(pb[i])]:
#                     print(f'{i}는 {j}의 접두어다.')
                    return not answer
        return answer   
        break

In [96]:

# pb = ["119", "97674223", "1195524421"]
pb = ["88","12", "123", "1235", "567", ]
# pb = ["123", "456", "789"]

In [97]:

solution5(pb)

['12', '123', '1235', '567', '88']
0 1

Out[97]:

False

수많은 삽질로 어찌저찌 되나 싶었지만 이것도 안됨. 시간초과로 틀렸다. 이젠 정말 답지 보는 것 밖에 없다...!!!

In [99]:

def solution(phone_book): 
    answer = True 
    phone_book.sort() 
    for i in range(len(phone_book)-1): 
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]: 
            answer = False 
            break 
            
    return answer

# 출처: https://somjang.tistory.com/entry/Programmers-정렬-전화번호-목록-Python [솜씨좋은장씨]

일단 while문과 이중for문이 없어서 깔끔하다. 처음엔 range(len(phone_book)-1)이 뭔가 했는데 보니까 i번째와 i+1번째 까지만 비교하면 되는거라 마지막에 하나 빼주는 걸 알게 되었다. 한 두시간 넘게 삽질만 한거 같은데 그래도 답지를 보니 아예 삽질한게 아니란 걸 느낀다.

In [102]:

# 또다른 풀이
# 출처: https://ychae-leah.tistory.com/47
def solution(phone_book):
    phone_book.sort()
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
    return True

zip, startswith가 눈에 띈다.

In [109]:

for a,b in zip(pb,pb[1:]):
    print(a,b)
print(pb,pb[1:])

12 123
123 1235
1235 567
567 88
['12', '123', '1235', '567', '88'] ['123', '1235', '567', '88']

In [111]:

for a,b in zip(pb,pb[1:]):
    if b.startswith(a):
        print(a,b)

12 123
123 1235

근데 함수가 허용 안되는 코딩테스트에는 이걸 쓸 수 있을 지 의문이다. 어쨌거나 새로운 걸 알았음.