baekjoon 5052: 전화번호 목록

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

5052번: 전화번호 목록

---

초기 구현 방법:

 

1. 완전탐색 but 시간초과
2. 그렇다면 전부 탐색하지 않게 조건문을 넣어줌. but 시간초과
3. sort를 사용 (단순 올림차순 sort, key를 len으로 둔 sort) but 시간초과

t = int(input())
for tc in range(t):
    n = int(input())
    arr = []
    lenArr=[0]*11
    for i in range(n):
        arr.append((input()))
    result = True

    arr.sort(key=lambda x: (len(x), x))

    for i in range(len(arr)):
        lenArr[len(arr[i])]+=1

    st = 0
    for i in range(len(lenArr)):
        if st >= len(arr):
            break

        if result ==False:
            break

        if lenArr[i] != 0:
            while lenArr[i] !=0:
                if result ==False:
                    break
                lenArr[i] -=1

                for j in range(st+1,len(arr)):
                    if arr[st] in arr[j]:
                        result = False
                        break
                st+=1
    if result ==False:
        print('NO')
    else:
        print('YES')

---

 

찾는 알고리즘에 큰 차이는 없지만, 문자마다 기준이 되는 문자의 해당 길이까지만을 검색하여 찾아주는 알고리즘을 다시 새로 짰다.

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

    for i in range(len(arr)-1):
        if arr[i] == arr[i+1][0:len(arr[i])]:
            print('NO')
            break
    else:
        print('YES')

어이없음