[백준] 2179 - 비슷한 단어

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

 

가장 긴 prefix를 구하는 건 쉬운데, 입력된 순서상 앞선 조합을 골라내는 것이 까다로운 문제

가장 긴 prefix를 구할 때는 단어를 정렬해서 한번 순회하면 O(n log n) 시간에 구할 수 있다.

 

이때 같은 길이의 prefix에 대해서 입력이 먼저된 단어를 출력해야 한다.

그래서 단어를 저장할 때, 입력된 순번도 같이 저장했다.

 

n = int(input())
l = []
for i in range(n):
    s = input().rstrip()
    l.append((s, i))

 

단어를 정렬하고 순회하면서 prefix를 체크할 때는 별도 함수를 사용했다.

이때 같은 prefix 를 갖는 단어들을 모두 저장하기위해 딕셔너리와 셋을 이용했다.

l.sort()
prefix_dict = dict()
max_length = 0
prefix_list = []
for i in range(1, n):
    prefix = check(l[i][0], l[i-1][0])
    prefix_len = len(prefix)
    if prefix_len < max_length:
        continue

    if prefix_len > max_length:
        prefix_list = []
        max_length = prefix_len

    prefix_list.append(prefix)
    if prefix not in prefix_dict:
        prefix_dict[prefix] = set()

    prefix_dict[prefix].add((l[i][1], l[i][0]))
    prefix_dict[prefix].add((l[i-1][1], l[i-1][0]))

 

prefix_dict 는 prefix 를 key로 해서, 그 prefix를 갖는 단어들의 집합을 value로 갖는다.

이때 이 집합에는 (입력된 순번, 단어) 쌍의 튜플이 저장된다.

순번을 먼저 저장해야 나중에 이 set을 정렬한 뒤, 앞에서부터 2개 단어를 뽑을 때, 먼저 입력된 순으로 2개 단어가 나온다.

 

prefix_list 는 현재 max_length 를 갖는 prefix 들의 리스트이다.

같은 길이의 서로다른 prefix가 존재할 수 있기 때문에 이렇게 처리하였다.

ans_idx = n
ans = None
for prefix_word in prefix_list:
    first, second = sorted(prefix_dict[prefix_word])[:2]
    if first[0] < ans_idx:
        ans = (first[1], second[1])
        ans_idx = first[0]

print(ans[0])
print(ans[1])

 

정답을 출력할 때는 prefix_list 를 순회하면서 저장한 max_length 길이의 prefix들을 딕셔너리에서 찾는다.

그리고 그 prefix를 갖는 먼저 입력된 단어 2개를 추출한다.

그 단어가 더 먼저 입력되었다면 정답 후보로 갱신해준다.

 

---

import sys
input = sys.stdin.readline

def check(s1, s2):
    prefix_chr = []
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]:
            prefix_chr.append(s1[i])
        else:
            break

    return "".join(prefix_chr)


n = int(input())
l = []
for i in range(n):
    s = input().rstrip()
    l.append((s, i))

l.sort()
prefix_dict = dict()
max_length = 0
prefix_list = []
for i in range(1, n):
    prefix = check(l[i][0], l[i-1][0])
    prefix_len = len(prefix)
    if prefix_len < max_length:
        continue

    if prefix_len > max_length:
        prefix_list = []
        max_length = prefix_len

    prefix_list.append(prefix)
    if prefix not in prefix_dict:
        prefix_dict[prefix] = set()

    prefix_dict[prefix].add((l[i][1], l[i][0]))
    prefix_dict[prefix].add((l[i-1][1], l[i-1][0]))


ans_idx = n
ans = None
for prefix_word in prefix_list:
    first, second = sorted(prefix_dict[prefix_word])[:2]
    if first[0] < ans_idx:
        ans = (first[1], second[1])
        ans_idx = first[0]

print(ans[0])
print(ans[1])