백준 - 문자열 게임 2 (20437); Java

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

20437번: 문자열 게임 2

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int i=0;i<T;i++) {
			String W = br.readLine();
			int K = Integer.parseInt(br.readLine());
			int min = 10001, max = 0;
			ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
			for(int a=0;a<26;a++) {
				list.add(new ArrayList<>());
			}
			
			//W 탐색 
			for(int j=0;j<W.length();j++) {
				int unicode = W.charAt(j) - 97;
				list.get(unicode).add(j);
				
				//어떤 알파벳(W[j])가 K번 나왔을 때 연속 문자열 길이를 구한다  
				int size = list.get(unicode).size();
				if(size >= K) {
					int start = list.get(unicode).get(size - K);
					int end = list.get(unicode).get(size-1);
					int len = end - start + 1;
					if(len<min) {
						//System.out.println("min: "+end+" "+start);
						min = len;
					}
					if(len>max) {
						//System.out.println("max: "+end+" "+start);
						max = len;
					}
				}
			}
			if(min==10001) {
				sb.append("-1\n");
				continue;
			}
			sb.append(min+" "+max+"\n");
		}
		System.out.println(sb.toString());
	}
}

각 문자마다 LinkedList<Integer>를 만들어줘서 문자가 나온 위치(idx)를 저장해준다. (Queue로 해도 될 듯)

현재 위치의 문자를 해당 문자의 LinkedList에 추가하고, 그 리스트 개수가 K개가 넘으면 탐색을 한다.

현재위치에서 K개 전~현재위치까지의 길이를 구한다.

 

나오지 않는 문자까지 LinkedList를 만들어주어서 메모리 소비가 크다.. ㅜ