[Java] 프로그래머스 [Level-4] [3차]자동완성

public class Solution {
	
	// [3차] 자동완성 // 테스트 케이스 부족, 시간 초과
	
	public static int strContainWordCnt(String[] words, String str) {
		int cnt = 0;
		
		for (String word : words) {
			
			if (word.contains(str)) {
				cnt++;
			}
			
			if (cnt > 1) return 2;
		}
		
		return cnt;
	}
	
	public static int solution(String[] words) {
		int answer = 0;
		String word = ""; // words 배열 속 원소
		StringBuilder sb = new StringBuilder(); // 문자열 비교를 위한 StringBuilder
        
		for (int i = 0; i < words.length; i++) { // words의 문자 하나씩 체크
			word = words[i];
			sb.setLength(0); // StringBuilder 초기화
        	
			for (int j = 0; j < word.length(); j++) {
				sb.append(word.charAt(j));
        		
//				if (Arrays.asList(words).contains(sb.toString())) // 배열이 특정 문자열을 포함하는지 여부를 확인할 때 사용
//        		
//					System.out.println(Collections.frequency(Arrays.asList(words), sb.toString())); // 이건 sb.toString()이 배열에 몇 개 들어있는지 체크네
//				
//				if (Collections.frequency(Arrays.asList(words), sb.toString()) == 1 || j == word.length() - 1) { // 특정 문자열을 포함하는 문자가 1개 남았거나, 2개 이상 남았어도 특정 문자열이 현재 i번째 word 자체인 경우
//					answer += j + 1; // j는 0부터 시작했으므로 개수는 + 1
//					break; // 안쪽 for문 탈출
//				} else {
//					continue;
//				}
        		
				if (strContainWordCnt(words, sb.toString()) == 1 || j == word.length() - 1) { // 특정 문자열을 포함하는 문자가 1개 남았거나, 2개 이상 남았어도 특정 문자열이 현재 i번째 word 자체인 경우
					answer += j + 1; // j는 0부터 시작했으므로 개수는 + 1
					break; // 안쪽 for문 탈출
				} else {
					continue;
				}
			}
		}
        
        return answer;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] words = {"worlll","warrior","war","word","world"}; // "abc","def","ghi","jklm" // 4 // a, d, g, j만 입력하면 자동완성 가능
		
		System.out.println(solution(words)); // 21
		
		// "worlll","warrior","war","word","world"
		// "worll" ,"warr"   ,"war","word","world" // 5 + 4 + 3 + 4 + 5
		
		// "worlll","warrior","war","word","world" // false false false false false
		// "w" 입력했을 때 후보 5개 (worlll길이보다 작아)
		// "wo" 입력했을 때 후보 3개 (worlll길이보다 작아)
		// "wor" 입력했을 때 후보 3개 (worlll길이보다 작아)
		// "worl" 입력했을 때 후보 2개 (worlll길이보다 작아)
		// "worll" 입력했을 때 후보 1개(5) (worlll길이보다 작아) // true false false false false
		// "w" 입력했을 때 후보 5개 (warrior길이보다 작아)
		// "wa" 입력했을 때 후보 2개 (warrior길이보다 작아)
		// "war" 입력했을 때 후보 2개 (warrior길이보다 작아)
		// "warr" 입력했을 때 후보 1개(4) (warrior길이보다 작아) // true true false false false
		// "w" 입력했을 때 후보 5개  (war길이보다 작아)
		// "wa" 입력했을 때 후보 2개 (war길이보다 작아)
		// "war" 입력했을 때 후보 2개 but war길이와 같아(3) // true true true false false
		// "w" 입력했을 때 후보 5개 (word길이보다 작아)
		// "wo" 입력했을 때 후보 3개 (word길이보다 작아)
		// "wor" 입력했을 때 후보 3개 (word길이보다 작아)
		// "word" 입력했을 때 후보 1개 and word길이와 같아(4) // true true true true false
		// "w" 입력했을 때 후보 5개 (world길이보다 작아)
		// "wo" 입력했을 때 후보 3개 (world길이보다 작아)
		// "wor" 입력했을 때 후보 3개 (world길이보다 작아)
		// "worl" 입력했을 때 후보 2개 (world길이보다 작아)
		// "world" 입력했을 때 후보 1개 and world길이와 같아(5) // true true true true true
		
		// 첫 번째 단어부터 마지막 단어까지 체크
		// 한 단어를 앞에서부터 차례로 자르면서 더하고 그 단어가 전체 단어 배열 중 몇 개의 단어와 일치할 수 있는지 판단
		// 후보가 1개이거나 or 2개 이상 존재할지라도 마지막 글자까지 잘라서 더한 상태라면(현재 단어 그 자체라면) 현재까지 자른 글자 수 카운트해서 더하기
	}
}

문자열 배열 {"AB", "ABC", "BC", "ZX"} 이 있을 때
문자열 "AB"를 포함하는 원소의 개수를 알고싶을 때
배열의 길이만큼 반복하며 체크하는 방법 외에
2를 바로 리턴받을 수 있는 방법이 있을까?

 

프로그래머스 자동완성 문제 풀이 Java 소스 코드