[백준] 5052번: 전화번호 목록

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

initial

sorting a list of strings is not like int. It compares the strings char by char with its lexicographical order. The first char that differs in the lexicographical order sorts the order. So even if you have like [“119”, “2” , “1195125125”], when it is sorted, the list becomes [“119”, “1195125125”, “2”] because 2 is lexicographically bigger than 1 so it is placed at the end. We compare char by char with the lexicographical order.

So if we have 2 strings that are lexicographically same or if 1 is a substring of another, this way works. We can check substring via “in” operator or .startswith() operator.

But the formal way to solve this is via Trie. tbc

solution

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

for _ in range(t):
    n = int(input())
    lst = []

    for _ in range(n):
        lst.append(input().rstrip())

    # Sorting a list of strings lexicographically
    lst.sort()
    flag=False
    for i in range(1, len(lst)):
        if lst[i].startswith(lst[i - 1]):
            
            flag=True
            break
    if flag:
        print("NO")
    else:
        print("YES")

using zip

instead of for loop you can use zip like this. We dont need to concern with the mismatch of length of 2 lists cuz when the shorter list is done iterating first, it substitutes the non existent value with None

for p1, p2 in zip(phoneBook, phoneBook[1:]):

using dictionary

I fidn this intuitive as well. We first mark all occrurrences as keys in a dictionary. Then we iterate through each string number char by char and append each char to a temporary string. If that temporary string, that is technically a substring of current nums string, is both not itself (i.e. not nums) and is present in our dict, then it is valid case cuz that means there is another key in a dictionary that has same string key as this substring.

def solution(phone_book): 
    # 1. Hash map 생성
    hash_map = {} 
    for nums in phone_book: 
        hash_map[nums] = 1 
    
    # 2. 접두어가 Hash map에 존재하는지 찾기 
    for nums in phone_book: 
        arr = "" 
        for num in nums: 
            arr += num
    
            # 3. 본인 자체일 경우는 제외
            if arr in hash_map and arr != nums:       
                return False 
                
    return True

revisited june 10th 24

i dont get the dict way but .startswith is useful

complexity

t n log n? yep

Let's analyze the time and space complexity of the provided code:

Time Complexity:
Input Reading (Line 1): O(1) - Reading an integer t.
Outer Loop (Line 3-10): O(t) - Iterating through each test case.
Inner Loop (Line 6-9): O(n log n) - Sorting the list of strings (lst) lexicographically.
Checking Prefixes (Line 11-14): O(n) - Iterating through the sorted list and checking if any string is a prefix of the string before it.
The dominant factor for time complexity is the sorting operation (O(n log n)), and the overall time complexity is O(t * (n log n)).

Space Complexity:
List of Strings (lst): O(n) - Space required to store the list of strings for each test case.
Loop Variables and Temporary Variables: O(1) - Constant space used for loop variables and temporary variables.
The overall space complexity is O(n) per test case.