[Baekjoon] 5052_전화번호 목록

Gold IV

문제(출처: https://www.acmicpc.net/problem/5052)

---

<전화번호 목록>

문제 

 

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

 

 

입력

 

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

출력 

 

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

 

 

문제 풀이

- 초기 코드: 틀렸습니다

 

import sys

if __name__=='__main__':
    t=int(input())

    for i in range(t):
        n=int(input())
        arr=[]
        min=10
        minarr=[]
        for j in range(n):
            str=sys.stdin.readline().replace(' ','').strip()
            arr.append(str)
            if min>len(str):
                min=len(str)
        for j in range(n):
            if len(arr[j])==min:
                minarr.append(arr[j])
            else:
                arr[j]=arr[j][:min]
        bool=False
        for j in minarr:
            if arr.count(j)>1:
                bool=True
        if bool==True:
            print("NO")
        else:
            print("YES")

 

 

문제를 본 후 쉽게 위와 같은 코드를 구현하였다. 한참 동안 생각해도 이유를 몰라서 멍하니 있었다.

질문 검색 게시판과 검색을 통해 다 봐도 찾을 수 없었다. 

 

처음에 찾은 이유는 '97 625 999'와 같이 공백 처리 때문이라고 하여 공백을 제거한 후 제출해봤지만 결과는 똑같았다.

 

❓ 왜 틀렸는가?

91123455

95

911

인 경우를 고려하지 않았었다. 내가 구현한 코드는 입력받은 전화번호 중 길이가 가장 짧은 값에 대해서만 일관성이 있는지 없는지 확인했기 때문이다. 이 부분을 알아차렸을 때 '와' 밖에 나오지 않았다.

 

 

- my solution

import sys

if __name__=='__main__':
    t=int(input()) # 테스트 케이스 개수

    for i in range(t):
        n=int(input()) # 전화번호 수
        arr=[]
        for j in range(n):
            str=sys.stdin.readline().replace(' ','').strip() # 입력
            arr.append(str)
        arr.sort() # 정렬
        bool=False # 일관성 check
        for j in range(n-1):
            if arr[j]==arr[j+1][:len(arr[j])]:
                bool=True
        if bool==True:
            print("NO")
        else:
            print("YES")

 

위에서 발견한 문제점을 해결하기 위해 정렬 후 비교하는 방법을 택하였다. 

왜 다들 정렬하는지 몰랐는데 위의 잘못된 이유를 알고나니 정렬을 사용해야 하는 이유를 알 수 있었다.

정렬 후 arr[j] 길이만큼 arr[j+1][:len(arr[j])]와 비교한 후 같으면 No를 출력해준다.

 

---

생각🤔

 

여러가지 경우를 생각해보도록 노력해야겠다는 생각이 들었다.

 

---