[백준/파이썬] 5052: 전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

문제 요약 : 테스트 케이스가 주어진다. 테스트 케이스의 첫 줄에는 전화번호의 수가 주어진다. 한 번호가 다른 번호의 접두어가 될 경우, 전화번호 목록의 일관성이 없다고 여긴다. 일관성이 없을 경우 "NO"를 있는 경우는 "YES"를 출력하라.

 

예제 입력 1 :

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

예제 출력 1 :

NO
YES

 

 

맞은 풀이는 밑에 풀이에 작성해 놨습니다!

시도1 )

처음에 문자열을 정렬해놓고 불필요하게 for문을 두번 돌렸다.

그 덕분에 시간초과..

 

for문을 두번 돌리지 않아도 되는 이유는 문자열을 sort한것이기 때문이다.

# 전화번호 목록
import sys
input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    number = []
    N = int(input().rstrip())
    
    for _ in range(N):
        number.append(input().rstrip())
    number.sort()
    answer = "YES"

    for i in range(len(number) - 1):
        for j in range(i+1,len(number)):
            if number[i] in number[j]:
                answer = "NO"
                break
    print(answer)

 

시도 2 )

여기서 엄청 고민을 많이 했다.

백준 질문게시판을 보니, 나와 같은 사람이 있었다.

왜 in이 안되냐고 질문을 해놓으셨는데, 답변을 해놓으신 분이 지우셨는지 답변은 볼 수 없었다.

 

안되는 이유는 접두어만 비교하는 것이 아닌 전부를 비교하기 때문이었다!😣

 

입력을

1

3

12

2312

89546

 

이렇게 두게 되면, 일관성이 있기때문에 "YES"가 출력되어야하지만, 12가 2312에 포함되어 있긴 해서 "NO"가 출력된다.

# 전화번호 목록
import sys
input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    number = []
    N = int(input().rstrip())
    
    for _ in range(N):
        number.append(input().rstrip())
    number.sort()
    answer = "YES"

    for n in range(len(number) - 1):
        if number[n] in number[n+1]:
            answer = "NO"
            break

    print(answer)

 

📌 풀이 )

문자열을 sort한 것이기 때문에 리스트 내 모든 문자와 비교할 필요없이 바로 다음 문자열과 비교하면 된다.

또한, 접두어이기 때문에 in이 아닌 문자열 슬라이싱을 통해 비교를 해주어야한다.

# 전화번호 목록
import sys
input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    number = []
    N = int(input().rstrip())
    
    for _ in range(N):
        number.append(input().rstrip())
    number.sort()
    answer = "YES"

    for n in range(len(number) - 1):
        if number[n] == number[n+1][:len(number[n])] :
            answer = "NO"
            break

    print(answer)