2179번: 비슷한 단어

• N개의 영단어가 주어진다 (2 ≤ N ≤ 20,000).
• 각 단어는 길이 100자 이하의 알파벳 소문자로만 이루어져 있다.
• 두 단어의 비슷한 정도는 공통 접두사의 길이로 측정한다.
• 공통 접두사 길이가 최대인 서로 다른 두 단어를 찾는다.
• 접두사 길이가 같은 경우가 여러 개면, 입력 순서가 가장 앞선 단어 쌍을 선택한다.
• 가장 비슷한 두 단어 S와 T를 출력한다 (S가 T보다 입력 순서가 앞서야 함).

접근

시간복잡도 계산해보기

N이 20,000으로 크기 때문에, 단순히 단어끼리의 비교를 하는데만 시간복잡도가 O(N^2)인데다가 접두사를 비교하게되면 최악으로는 단어길이 100이 곱해지기 때문에 불가능하다 판단하였다.
시간내에 통과하기 위해서는 S = 단어길이라고 했을 때, 시간복잡도는 리니어하거나 최대 로그 시간복잡도를 가진 O(N*S) ~ O(N*logN*S)가 되어야했다.

방법 찾기

1. 이분탐색
각 단어별로 알파벳 순으로 정렬된 단어배열에서 접두사를 비교하는 방법을 생각해보았다. 하지만 단어의 길이에 따른 출력이 아닌 입력순으로 출력이 되어야하기 때문에, 정렬 후 탐색하면서도 입력순서도 고려해야했기에는 탐색이 너무 복잡해진다 생각했다. 따라서, 다른 방법을 찾아보았다.

2. 접두사 맵
각 단어끼리의 접두사 비교는 단어가 입력될 때마다 이전 단어에 대해 수행이 되면 된다. 다만, 모든 단어에 대해 연산을 하면 시간복잡도가 O(N^2)이 된다. 그렇기에 지금까지 입력된 단어 중에 동일한 접두사를 가졌었는지 확인하는 효율적인 방법이 필요했고, O(1)로 확인이 가능한 Map을 사용했다.

단어가 입력될 때마다 가장 긴 접두사(부분문자열)부터 Map에 접두사가 저장되어 있는지 확인한다:

1. 없다면, Map에 부분문자열과 함께 현재 단어를 저장한다.
2. 있다면 :
   a. 부분 문자열의 원본 단어가 현재 단어와 같은지 확인한다. (같으면 안된다)
   b. 기존 접두사 길이보다 길거나 / 길이와 같고, 저장된 접두사의 입력순서가 S보다 빠르다면:
   • Map에 저장된 접두사의 원본 단어가 S
   • 지금 입력된 단어가 T
   • 접두사 길이 갱신

입력된 순서는 단어별로 바로 탐색이 가능하도록 별도의 Map으로 관리한다.
Map으로 인해 메모리 사용량이 높을 수 있지만, 그 대가로 O(N*S) 수준의 리니어한 수행속도를 보장한다.

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        solve(in);
    }
    
    static void solve(BufferedReader in) throws IOException {
    	int cnt = Integer.parseInt(in.readLine());
    	Map<String, Integer> order = new HashMap();
    	Map<String, String> map = new HashMap<>();
    	
    	int max = 0;
    	String first = "";
    	String second = "";
    	
    	for(int i = 0; i < cnt; i++) {
    		String str = in.readLine();
    		
    		if(!order.containsKey(str)) order.put(str, i);
    		
    		for(int s = str.length(); s > 0; s--) {
    			String sub = str.substring(0, s);
    			
    			if(!map.containsKey(sub)) map.put(sub, str);
    			else {
    				if(!map.get(sub).equals(str) 
    						&& (sub.length() > max 
    								|| (sub.length() == max && order.get(map.get(sub)) < order.get(first)))) {
    					first = map.get(sub);
    					second = str;
    					max = sub.length();
    				}
    				break;
    			}
    		}
    	}
    	
    	System.out.println(first);
    	System.out.println(second);
    }
}

회고

• 자료구조를 통해 시간복잡도를 매우 줄일 수 있는 문제였다.