카카오 신입 공채 3차 5번 문제

문제5. 자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go
gone
guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 형식

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다. 모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

출력 형식

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

입출력 예제

words	result
[“go”,”gone”,”guild”]	7
[“abc”,”def”,”ghi”,”jklm”]	4
[“word”,”war”,”warrior”,”world”]	15

입출력 설명

• 첫 번째 예제는 본문 설명과 같다.
• 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
• 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
  • word는 word 모두 입력해야 한다.
  • war는 war 까지 모두 입력해야 한다.
  • warrior는 warr 까지만 입력하면 된다.
  • world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)

문제 해설

3차 코딩 테스트에서 가장 어려운 문제였습니다. 열심히 코딩한 후에 제출하면 시간 제한에 걸려 좌절하는 지원자가 많았습니다. 두 단어 “world”와 “word”가 앞 세 글자가 겹친다는 걸 찾는 건 어렵지 않지만, 모든 단어 쌍을 비교하는 방식으로는 제한 시간 내에 풀 수 없습니다.

이 문제 해결에 적합한 자료 구조로 트라이^Trie가 있습니다. 입력으로 주어진 단어로 트라이를 구성하면, 같은 접두어^Prefix를 갖는 단어가 얼마나 있는지를 효과적으로 찾을 수 있습니다.

또 다른 방법이 하나 더 있는데요. 전체 단어를 사전 순으로 정렬한다면, 어떤 단어와 앞부분이 가장 많이 일치하는 단어는 정렬 후 인접한 두 단어 중 하나가 됩니다. 이 방법을 이용하면 모든 단어 쌍이 아닌, 정렬 후에 인접한 단어 쌍만 비교하면 되므로 빠르게 문제를 해결할 수 있습니다.

이 문제의 정답률은 34.07%였습니다. Java 사용자들이 가장 잘 풀었습니다.

---

어려운 문제는 아닌데, 위의 문제 해설 대로 제한 시간 내에 풀기 위한 방법을 궁리하는게 핵심인 듯 하다.

쉽게 풀었네! 하면서 문제 해설을 보니 시간 초과 문제를 해결하라고 한다. 사전 정렬이 된 경우, 앞 뒤만 검색하면 되는데 정렬을 해놓고서도 앞, 뒤만 검색한다는 생각을 하지 않았던 것이 실수다.

전체 탐색 버전

package kakao02;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Vector;

public class kakao02 {
	static int Answer;

	public static void main(String args[]) throws Exception {

		String[] input1 = new String[] { "go", "gone", "guild" };
		String[] input2 = new String[] { "abc", "def", "ghi", "jklm" };
		String[] input3 = new String[] { "word", "war", "warrior", "world" };
		int answer1 = Solution(input1);
		int answer2 = Solution(input2);
		int answer3 = Solution(input3);
		System.out.println(answer1);
		System.out.println(answer2);
		System.out.println(answer3);
	}

	public static int Solution(String[] words) {
		List<String> wordV = (List<String>) Arrays.asList(words);
		int maxCount = 0;
		Collections.sort(wordV);
		for (int i = 0; i < wordV.size(); ++i) {
			int j;
			for (j = 1; j < wordV.get(i).length(); ++j) {
				Boolean collision = false;
				for (int k = 0; k < wordV.size(); ++k) {
					if (k != i && wordV.get(k).contains(wordV.get(i).substring(0, j))) {
						collision = true;
						break;
					}
				}
				if (collision == false) {
					maxCount += j;
					break;
				}
			}
			if (j == wordV.get(i).length())
				maxCount += j;
		}
		return maxCount;
	}
}

일부 탐색 버전

package kakao02;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Vector;

public class kakao02 {
	static int Answer;

	public static void main(String args[]) throws Exception {

		String[] input1 = new String[] { "go", "gone", "guild" };
		String[] input2 = new String[] { "abc", "def", "ghi", "jklm" };
		String[] input3 = new String[] { "word", "war", "warrior", "world" };
		int answer1 = Solution(input1);
		int answer2 = Solution(input2);
		int answer3 = Solution(input3);
		System.out.println(answer1);
		System.out.println(answer2);
		System.out.println(answer3);
	}

	public static int Solution(String[] words) {
		List<String> wordV = (List<String>) Arrays.asList(words);
		int maxCount = 0;
		Collections.sort(wordV);
		for (int i = 0; i < wordV.size(); ++i) {
			int j;
			for (j = 1; j < wordV.get(i).length(); ++j) {

				Boolean collision = false;

				if (i != 0) {
					if (wordV.get(i - 1).contains(wordV.get(i).substring(0, j))) {
						collision = true;
					}
				}
				if(i != wordV.size()-1)
				{
					if (wordV.get(i + 1).contains(wordV.get(i).substring(0, j))) {
						collision = true;
					}
				}
				if(collision == false)
				{
					maxCount+=j;
					break;
				}
			}
			if (j == wordV.get(i).length())
				maxCount += j;
		}
		return maxCount;
	}
}