[BOJ] Q2179 비슷한 단어

[BOJ] Q2179 비슷한 단어

Question

Language: Python

Difficulty: Gold 5

최대 접두어를 갖는 단어의 쌍을 찾는 문제로, sorting을 통해 문제를 해결하는 것이 가능하다. sorting을 통해 문자열을 순서대로 정렬을 수행하고, 각 인덱스에서 가질 수 있는 최대 접두어의 길이를 초기화한다.

이후, 해당 길이를 가지는 인덱스를 추출하는 방식으로 문제를 해결하는 것이 가능하다.

Solution 1

def count_prefix(word1,word2):
    length=min(len(word1),len(word2))
    count=0
    for index in range(length):
        if word1[index]==word2[index]:
            count+=1
        else:
            break
    return count

def solution():
    sorted_words=sorted(words)
    length=[0] * n

    #각각의 문자열이 가질 수 있는 최대 접두어 길이를 구한다.
    for index in range(1,n):
        previous_word,previous_index=sorted_words[index-1]
        current_word,current_index=sorted_words[index]
        prefix_size=count_prefix(previous_word,current_word)

        length[previous_index]=max(length[previous_index],prefix_size)
        length[current_index]=max(length[current_index],prefix_size)

    max_prefix_cont=max(length)

    #처음부터 탐색을 진행해서 최대 접두어 길이와 동일한 접두어의 길이를 가지는 단어를 찾는다.
    first,second="",""
    prefix=""
    for i in range(n):
        if first == "":
            if length[i]==max_prefix_cont:
                first=words[i][0]
                prefix=words[i][0][:max_prefix_cont]
                continue
        else:
            if length[i]==max_prefix_cont and words[i][0][:max_prefix_cont] == prefix:
                second=words[i][0]
                break
        
    print(first)
    print(second)             
      
if __name__ == "__main__":
    n=int(input())
    words=[(input().strip(),i) for i in range(n)]
    
    solution()

Solution 2

단어의 갯수가 최대 2만개, 각 길이는 100이하이므로 모든 prefix에 대해 조사를 해도 충분히 시간 복잡도 내에 해결하는 것이 가능하다.

from collections import defaultdict
def solution():
    prefix_map=defaultdict(list)

    #모든 prefix에 대한 조사 실시
    for word_index in range(n):
        word=words[word_index]
        for letter_index in range(1,len(word)+1):
            prefix_map[word[:letter_index]].append(word_index)
    
    #각 prefix에 대해서, prefix 길이, first, second index를 추출하여 나중에 정렬을 통해 최대 prefix 길이, 가장 빠른 first, second index 순서쌍을 찾는다.
    candidates=[]
    for prefix in prefix_map:
        word_list=prefix_map[prefix]
        if len(word_list) >= 2:
            candidates.append((len(prefix),word_list[0],word_list[1]))
    
    candidates.sort(key=lambda x:(-x[0],x[1],x[2]))

    _,first_index,second_index=candidates[0]
    print(words[first_index])
    print(words[second_index])

if __name__ == "__main__":
    n=int(input())
    words=[input().strip() for _ in range(n)]
    
    solution()