99클럽 코테 스터디 16일차 TIL - 비슷한 단어(백준 #2179)

❇️오늘의 학습 키워드 : 비슷한 단어(백준 #2179)

문제

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

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

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

입력

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

출력

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

예제 입력 1 

9
noon
is
lunch
for
most
noone
waits
until
two

예제 출력 1 

noon
noone

예제 입력 2 

4
abcd
abe
abc
abchldp

예제 출력 2 

abcd
abc

정답 코드(블로그 참고)

n = int(input())
a = [input() for _ in range(n)] # 원본
b = sorted(list(enumerate(a)),key = lambda x: x[1]) # 인덱스와 같이 저장 + 알파벳 순 정렬
# 정렬하는 이유: 모든 문자열 쌍을 다 비교하지 않고 인접한 문자열끼리만 비교하면 되므로

def check(a, b): # 앞에서부터 겹치는 최장 길이 체크하는 함수
    cnt = 0
    for i in range(min(len(a), len(b))): # 인덱스 범위 초과하지 않게 더 짧은 걸 기준으로 비교해야됨
        if a[i] == b[i]:
        	cnt += 1
        else:
        	break
    return cnt
    
length = [0] * (n+1) # 최장 접두사를 가진 문자열 담아둘 리스트(인덱스에 len저장)
maxlength = 0

for i in range(n-1):
    tmp = check(b[i][1], b[i+1][1]) # 본인과 다음꺼만 비교
    maxlength = max(maxlength, tmp)
   
    length[b[i][0]] = max(length[b[i][0]], tmp)
    length[b[i+1][0]] = max(length[b[i+1][0]], tmp)
    
first = 0
for i in range(n):
    if first == 0:
        if length[i] == max(length):
            first = a[i]
            print(first)
            pre = a[i][:maxlength] # 공통되는 부분 저장(두번째 문자열 출력 위해)
    else:
        if length[i] == max(length) and a[i][:maxlength] == pre: # 최장+저장해두었던 공통되는 부분과 일치
            print(a[i])
            break

❇️오늘의 회고

  - 항해99 코테스터디 덕분에 매일 알고리즘 문제를 푸는 습관이 생겼다! 안 참여했으면 더 루즈해지지 않았을까 싶다...

  - 문자열을 정렬한다는 획기적인 아이디어는 어떻게 얻는 것인지...오늘도 벽을 느낀다...

  - 내일 11시, 문제를 풀기 전에 위 문제를 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂