[JAVA 자바] 백준 2179

 

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

2179번: 비슷한 단어

 

가장 먼저 떠오른 방법은 모든 문자의 모든 경우를 구하는 방법이다. 하지만 입력길이가 20000이기 때문에 N * N * 100으로 시간초과가 난다고 판단했다.

 

떠오른 방법은 문자를 1자리 2자리 3자리 ...N자리로 다 나누고 set에 넣어 비교하는 방식을 생각했다. S와 T를 저장해서 출력해야 하는데 이 방식은 접두사가 같은 문자를 찾아도 S를 찾을 수가 없었다.

 

결국은 Map에서 키로 자른문자 value로 원본문자를 넣어서 S와 T를 찾는 방식으로 풀었다. 제출하면서 매번 split을 하니 메모리초과를 걱정했는데 무사통과했다.

 

 

import java.io.*;
import java.util.*;
class Main {
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int cnt = 0;
        HashMap<String, String> map = new HashMap<>();
        String S = "";
        String T = "";
        for (int i = 0; i < N; i++) {
            String word = br.readLine();
            for (int j = 0; j < word.length(); j++) {
                String s = word.substring(0,j+1);
                if(map.containsKey(s)){
                    if(s.length() > cnt){
                        S = map.get(s);
                        T = word;
                        cnt = s.length();
                    }
                }else map.put(s,word);
            }
        }
        System.out.println(S);
        System.out.println(T);
    }
}