🦊 비슷한 단어

1. 문제 링크

2469번: 비슷한 단어

2. 코드

N = int(input())

words = []
length = 30000
for i in range(N):
    word = input()
    words.append(word)

S = -1
T = -1
max_count = -1
for i in range(N):
    left = words[i]
    for j in range(i + 1, N):
        right = words[j]
        count = 0
        length = min(len(left), len(right))
        if left == right or left[0] != right[0]:
            continue
        for k in range(length):
            if left[k] != right[k]:
                break
            count += 1
        # 최대 접두사 갱신
        if max_count < count:
            max_count = count
            S = i
            T = j

# 앞에서 부터 최대 접두사를 가지고 찾음
print(words[S])
print(words[T])

3. 해설

pypy3 112490kb 3136ms

• 해설

  딕셔너리로 최적화했다가 자꾸 틀려서 O(N^2)로 수정….

  문자열을 완전 탐색하여 최대 접두사 길이를 갱신하고 인덱스를 저장

  구한 인덱스를 최종으로 출력