[프로그래머스] [3차] 자동완성 (자바)

 

https://programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

 

 

약 34%의 정답률인 문제입니다.

레벨 4치고는 매우 쉬운 문제였습니다.

카카오에서는 이 문제를 풀기 위한 자료구조로 트라이(Trie)를 소개해줬습니다.

문제를 풀 당시에는 이런 자료구조를 모르고 풀었습니다.

 

입력된 단어들을 사전 순으로 정렬하여 특정 단어의 앞, 뒤 단어와 겹치는 부분을 검사하고, 최댓값을 통하여 해당 단어의 최소 입력 횟수를 구할 수 있었습니다.

예를 들어 2번째 단어에서

1. "abc", "abcd", "abcdf"의 경우 겹치는 최대값이 4입니다.
2. "abc", "adef", "adzzzzz"의 경우 겹치는 최대값이 2입니다. 즉, 3개를 입력해야 합니다.
3. "abc", "abcd", "ddd"의 경우 겹치는 최대값은 3입니다. 즉, 4개를 입력해야 합니다.

---

메소드

void solution

ArrayList에 단어들을 넣고 사전 순으로 정렬합니다. (words를 그냥 정렬해도 됩니다.)

answer는 총 입력 횟수이고 value는 해당 단어의 입력 횟수를 구하기 위한 임시 값입니다.

구하고자 하는 단어의 앞, 뒤 단어와 겹치는 부분을 구하고 최댓값이 단어의 길이와 같다면 최댓값을

같지 않다면 최댓값 + 1을 answer에 더해줍니다.

int len

단어 s1, s2의 겹치는 부분을 더하여 반환해줍니다.

 

import java.util.*;

class Solution {
	public static int solution(String[] words) {
		int answer = 0;
		int value = 0;
		ArrayList<String> al = new ArrayList<String>();

		for(String word : words)
			al.add(word);
		Collections.sort(al);

		value = len(al.get(0), al.get(1));
		if(value < al.get(0).length())
			answer += value + 1;
		else
			answer += value;

		for(int i = 1; i < words.length - 1; i++) {
			value = len(al.get(i), al.get(i-1));
			value = Math.max(len(al.get(i), al.get(i+1)), value);

			if(value < al.get(i).length())
				answer += value + 1;
			else
				answer += value;
		}
		
		value = len(al.get(words.length - 2), al.get(words.length - 1));
		
		if(value < al.get(words.length-1).length())
			answer += value + 1;
		else
			answer += value;

		return answer;
	}

	public static int len(String s1, String s2) {
		int length = 0;
		for(int i = 0; i < s1.length() && i < s2.length(); i++) {
			if(s1.charAt(i) == s2.charAt(i))
				length++;
			else
				break;
		}

		return length;
	}

}