[백준]#5052 Python

백준 5052번 - 전화번호 목록

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

전체 코드

import sys
input = sys.stdin.readline


def consistency(array):
    for i in range(len(array)-1):
        compare = array[i][0]
        compare_length = array[i][1]

        for s in range(i+1, len(array)):
            check = True
            idx = 0
            while idx < compare_length:
                if array[s][0][idx] == compare[idx]:
                    idx += 1
                else:
                    check = False
                    break

            if check:
                return False
    
    return True


t = int(input())
for i in range(t):
    n = int(input())
    ph = []
    for s in range(n):
        num = input().rstrip('\n')
        ph.append((num, len(num)))

    ph = sorted(ph, key=lambda x: x[1])
    if consistency(ph):
        print('YES')
        continue
    else:
        print('NO')
        continue

사실 Python3로 돌리니 시간초과가 나온 코드이다,,, 다행히 Pypy3로 돌리니 맞았다고는 뜨지만 여전히 기분히 찜찜하긴 하다.

접근법

• 전화번호를 길이 순서로 정렬해준다.
• 이중 for 문으로 서로 다른 두개의 전화번호를 선택해서 비교 -> 이 부분에서 시간초과가 나지 않았나 싶다.
• 같은 인덱스의 숫자가 같으면 인덱스값 증가, 다르면 다음 전화번호로 넘어간다.
• while 문을 통과해서 check 가 True 인 채로 넘어가면 해당 전화번호가 다른 전화번호에 포함되어 있다는 말이므로 함수 종료.

모범답안

import sys
input = sys.stdin.readline
t = int(input())

def check():
    for i in range(len(a)-1):
        if a[i] == a[i+1][0:len(a[i])]:
            print('NO')
            return
    print('YES')

for _ in range(t):
    n = int(input())
    a = []
    for i in range(n):
        a.append(input().strip())
    a.sort()
    check()

느낀점

문자열을 정렬시키면 사전순으로 배열, 사전 순에 구애받지 않는 경우 길이가 짧은 숫자가 먼저 배열. 따라서 이 문제에서는 배열만 시키면 i, i+1 끼리만 비교해주면 된다.