[ BOJ ] 2179 : 비슷한 단어 ( GOLD 4 ) / Python

문제

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

입력

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

출력

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

풀이 과정

공통 접두사의 길이를 비슷한 정도로 측정하기에, 문자열을 정렬한 뒤 가장 비슷한 두 단어를 브루트포스로 구했다.

S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력해야 한다는 점을 유의해야 한다. 

 

처음엔 정렬한 뒤 인접한 단어들의 비슷함 정도만 측정하려 했지만, aab / aa / aaa 순으로 입력되면 aab aaa 가 출력될 수 있다. ( 정답은 aab / aa )

aa - aaa - aab 순으로 정렬되면 비슷함 정도가 모두 2이므로 먼저 입력된 aab aaa 쌍이 출력되기 때문이다. 이 반례를 통해 정렬했을 때 인접한 단어만 측정하면 안 된다는 것을 알 수 있다.

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
words = [[list(input().rstrip()), i] for i in range(n)]

words.sort(key=lambda x:(x[0], x[1]))
max_cnt = -1
max_num = [-1, -1]
max_idx = [-1, -1]
for i in range(n-1):
    for j in range(i+1, n):
        cnt = 0
        while len(words[i][0]) > cnt and len(words[j][0]) > cnt and words[i][0][cnt] == words[j][0][cnt]: cnt += 1
        if cnt == 0: break
        
        if max_cnt < cnt:
            max_cnt = cnt
            max_num = [words[i][1], words[j][1]]
            max_idx = [i, j]
        elif max_cnt == cnt:
            if min(max_num) > min(words[i][1], words[j][1]):
                max_num = [words[i][1], words[j][1]]
                max_idx = [i, j]
            elif min(max_num) == min(words[i][1], words[j][1]) and max(max_num) > max(words[i][1], words[j][1]):
                max_num = [words[i][1], words[j][1]]
                max_idx = [i, j]

if max_num[0] < max_num[1]: 
    print(''.join(words[max_idx[0]][0]))
    print(''.join(words[max_idx[1]][0]))
else:
    print(''.join(words[max_idx[1]][0]))
    print(''.join(words[max_idx[0]][0]))