[99클럽 코테 스터디 2일차 TIL] 백준 - 2179.비슷한 단어

체감 난이도 : 중

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

예제 입력1

9
noon
is
lunch
for
most
noone
waits
until
two

예제 출력1

noon
noone

실패 과정

처음에는 N의 최대가 20,000라 시간복잡도가 O(n^2)이 되면 안된다고 판단했습니다.
그래서, 완탐이 아닌 HashMap과 Set을 사용해서 푸는 것을 생각하고 진행했습니다.

그런데 이렇게하니, 입력된 순서대로 출력해야하는 부분을 처리하기 어려워졌습니다.

아래는 실패한 코드입니다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(reader.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		List<String> list = new ArrayList<>();
		
		for (int i=0; i < N; i++) {
			String input = reader.readLine();
			list.add(input);
		}
		
		String[] answer = new String[2];
		
		answer[0] = list.get(0);
		answer[1] = list.get(1);
		
		solution(list, 1, answer);
		System.out.println(answer[0]);
		System.out.println(answer[1]);
	}
	
	public static void solution(List<String> list, int len, String[] answer) {
		HashMap<String, List<String>> map = new HashMap<>();
		boolean check = false;
		for (int i = 0; i < list.size(); i++) {
			if (list.get(i).length() < len) continue;
			
			map.putIfAbsent(list.get(i).substring(0, len), new ArrayList<>());
			map.get(list.get(i).substring(0, len)).add(list.get(i));
			
			if (map.get(list.get(i).substring(0, len)).size() == 2 && !check) {
				answer[0] = map.get(list.get(i).substring(0, len)).get(0);
				answer[1] = map.get(list.get(i).substring(0, len)).get(1);
				check = true;
			}
		}
		
		List<String> temp = new ArrayList<>();
		List<String> keys = new ArrayList(map.keySet());
		int maxLen = 0;
		for (String key : keys) {
			if (map.get(key).size() >= 2) {
				for (String str : map.get(key)) {
					temp.add(str); // 여기서 문자열의 순서가 섞입니다.
					
					if (maxLen < str.length()) maxLen = str.length();
				}
			}
		}
		
		if (temp.size() == 0 || len == maxLen) {
			return;
		} 
		
		solution(temp, len+1, answer);
	}
}

재귀로 호출될때마다 후보가 되는 문자열을 새로 temp에 넣습니다.
map의 값인 List에서는 입력되는 순서를 유지할 수 있는데, map 전체적으로보면 순서를 알 수 없습니다. 순서를 유지하기위해서 문자열의 index값을 같이 저장할까 고민했는데, 처리하기 복잡하다는 생각이 들었습니다.

그래서 다시 문제를 살펴보니, 시간제한이 2초입니다.
그냥 완탐으로 O(n^2)으로 풀면됩니다.

문제분석

문자열 순서대로 하나씩 비교하면서, 정답값을 갱신합니다.
배열 끝까지 탐색합니다.

설계

기준 문자열을 잡고, 기준 문자열 이후의 모든 문자열과 비교합니다.
문자열의 문자를 앞에서부터 하나씩 비교해서 공통 접두사 길이를 구합니다.

최대 공통 접두사 길이보다 현재 공통 접두사 길이가 크다면, 정답 문자열과 최대 공통 접두사 길이를 갱신합니다.

위 과정을 모든 문자열끼리 비교되도록 반복합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        List<String> stringList = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            String inputString = bufferedReader.readLine();
            stringList.add(inputString);
            
        }

        int resultIndex1 = 0;
        int resultIndex2 = 0;
        int maxCount = 0;
        
        for (int i = 0; i < n; i++) {
            String str1 = stringList.get(i);
            
            for (int j = i + 1; j < n; j++) {
                int count = 0;
                String str2 = stringList.get(j);
                int size = Math.min(str1.length(), str2.length());
                
                for (int z = 0; z < size; z++) {
                    if (str1.charAt(z) == str2.charAt(z)) {
                        count++;
                    } else {
                        break;
                    }
                }
                
                if (count > maxCount) {
                    resultIndex1 = i;
                    resultIndex2 = j;
                    maxCount = count;
                }
            }
        }

        System.out.println(stringList.get(resultIndex1));
        System.out.println(stringList.get(resultIndex2));
    }
}

공부한 사항

• Set이나 Map을 사용하지 않아도, List에 특정 값이 포함되어 있는지 확인할 수 있다.
  : contains()
  : indexOf() 를 사용해서, -1이 나오면 없는 원소