[백준/2179] 비슷한 단어 (Python)

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

2179번: 비슷한 단어

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:40:52

 

---

 

문제 설명

 

 

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

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

9
noon
is
lunch
for
most
noone
waits
until
two

 

출력 예시

 

noon
noone

 

 

---

 

풀이

 

처음에는 브루트포스로, 즉 O(N^2)으로 푸는 게 가능하겠거니 싶었다. 안일했다... 나중에 찾아보니 C++코드 등은 통과되는 경우가 있는 것 같은데, 유감스럽게도 파이썬 환경에서는 힘들다.

 

즉 다른 방식을 사용해야 한다.

사전순으로 정렬을 시행(O(NlogN))하면 접두어가 유사한 단어끼리 배치되므로, 인접한 단어를 비교하는 경우를 통해 최대 접두사 길이를 쉽게 구해낼 수 있다. 이 때, 정렬 전의 순서가 중요하므로 최소 index를 저장해두어야 한다.

 

또한 다음과 같은 반례를 고려해야 한다.

aabbd

aabb

aabbc

 

이를 사전순으로 정렬하면

aabb

aabbc

aabbd

가 되고, 인접 index만을 참조하게 되면 아마

 

aabbd

aabbc

 

라는 오답을 내뱉게 될 것이다. 즉 최소 index의 최대 길이 접두사를 얻었다면 리스트 전체에서 위 조건에 포함되는 단어들을 고려해야 한다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
words = [(input().strip(), i) for i in range(N)]
prefix = ''
answer_min_idx = float('inf')
words.sort()

for i in range(N-1) :
  if words[i][0] == words[i+1][0] :
    continue
  maxlen = min(len(words[i][0]), len(words[i+1][0]))
  min_idx = min(words[i][1], words[i+1][1])
  for j in range(maxlen) :
    if words[i][0][j] != words[i+1][0][j] :
      break
    if j == maxlen-1 :
      j += 1
  if len(prefix) < j or len(prefix) == j and min_idx < answer_min_idx :
    prefix = words[i][0][:j]
    answer_min_idx = min_idx

answer = list()
for word, idx in words :
  if word[:len(prefix)] == prefix :
    answer.append((word, idx))
answer.sort(key = lambda x : x[1])
for word in answer[:2] :
  print(word[0])

풀이 완료!