99클럽 코테 스터디 1일차 TIL / 비슷한 단어

비슷한 단어

시간 제한 : 2초
메모리 제한 : 128MB

학습 키워드 : 해시맵구조, 문자열처리, 정렬

문제

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

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

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

입력

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

출력

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

풀이

메모리 : 32548kb
시간 : 88ms

2초의 시간제한과 N의 최댓값이 20000이므로 시간복잡도 O(N^2)을 피하고자 했다. 코드와 함께 주석으로 설명.

코드

import sys
input = sys.stdin.readline

#word_dict : key값 = word , value = 겹치는 접두사의 최대 길이
word_dict = {}

# 입력받고 value를 0으로 초기화
N = int(input())
for _ in range(N):
    now = input().rstrip()
    word_dict[now] = 0

# word_cnt_list : word_dict의 word를 sorted로 사전 순서대로 배열한다.
#-> **사전순서대로 배열해서 인접한 string끼리만 비교해서 시간복잡도를 크게 줄일 수 있다.**
word_cnt_list = sorted([word for word in word_dict])

# max_cnt : 겹치는 접두사의 길이의 최댓값. 나중에 dictionary를 순회하면서 value가 max_cnt인 item만 비교할 예정
max_cnt = 0
for idx, word in enumerate(word_cnt_list):
	# IndexERROR를 피함
    if idx == N-1:
        break
    now, compare = word_cnt_list[idx], word_cnt_list[idx+1]
	#max_len : now,compare중 더 짧은 길이만큼만 순회
    max_len = min(len(now),len(compare))
    #for 루프를 돌면서 word_dict의 값 초기화
    for i in range(max_len):
		# 같은 경우 continue
        # 한 string이 다른 string에 포함되는 경우. i값으로 초기화가 되지 않는 문제가 존재해서 if문으로 초기화
        if now[i] == compare[i]:
            if i == max_len-1:
                word_dict[now] = max(word_dict[now],max_len)
                word_dict[compare] = max_len
                max_cnt=max(max_cnt,max_len)
            continue
        else:
        	#글자가 다른경우 word_dict에 초기화
            word_dict[now] = max(word_dict[now],i)
            word_dict[compare] = i
            max_cnt=max(max_cnt,i)
            break
            

# chk : S가 정해졌는지 확인용
chk = 0
S,T = str(),str()
# dictionary를 순회하면서 value가 max_cnt인 key찾기
# S가 정해졌으면 S의 접두사와 같은 접두사를 갖는 T찾기
for k,v in word_dict.items():
    if v == max_cnt:
        if chk == 0:
            S=k
            chk = 1
        elif S[:max_cnt]==k[:max_cnt]:
            T = k
            break
print(S)
print(T)

시간복잡도

1. word_dict 초기화 : O(N)
2. word_dict_cnt 초기화 : O(NlogN+N) ~= O(NlogN)
3. 접두사 비교 파트 : O(NL)
4. 최대 길이를 가진 공통 접두사 찾기 : O(N)

O(N^2)의 시간복잡도를 가지지 않음.

코멘트

백준 알고리즘 분류에서 힌트를 얻어서(ㅎㅎ;;) 사전순으로 정렬하는 방법으로 접두사의 길이를 비교했다.