문제 Gold 5

문제보기

풀이

3, 4 조건이 다르게 보일 수 있지만, 3번 역시 가장 짧은 문자열이려면 첫번째와 마지막 문자가 해당 문자여야 한다!

💡 따라서, 3,4번이 동일한 조건이고 그 조건의 가장 짧은, 긴 길이만 구해주면 된다.

1. 알파벳들이 나온 인덱스를 모두 저장할 수 있도록 리스트 배열을 선언한다.
2. 알파벳을 돌면서 리스트에 인덱스들을 add 한다!
   • Add 후, 리스트 사이즈가 K라면 3, 4번 조건을 모두 충족하게 됨
   • 3번 결과인 min과 4번 결과인 max 값을 갱신
   • 갱신 후, 문자가 K개 이상이 들어가면 안되므로 맨 처음에 들어간 값은 빼줌!
3. min과 max 값이 바뀌지 않았다면 조건에 만족되는 문자열이 없었다는 것이므로 -1 출력

코드

package implement;

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

public class BOJ_20437_문자열게임2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for(int tc = 0 ; tc < T ; tc++){
            String W = br.readLine();
            int K = Integer.parseInt(br.readLine());
            List<Integer>[] alpha = new List[26];
            for(int i =0 ; i < 26 ; i ++) alpha[i] = new ArrayList<>();
            int min = Integer.MAX_VALUE;    // 3번 조건
            int max = Integer.MIN_VALUE;    // 4번 조건

            for(int i =0 ; i < W.length() ; i++){
                int idx = W.charAt(i)-'a';
                alpha[idx].add(i);  // 알파벳 배열에 인덱스 추가
                if(alpha[idx].size() == K){ // 3,4번 조건을 만족한다면!
                    int length = i - alpha[idx].get(0) + 1;
                    min = Math.min(length, min);    // 3번 결과값 갱신
                    max = Math.max(length, max);    // 4번 결과값 갱신
                    alpha[idx].remove(0);   // 맨 처음 들어온 인덱스 삭제
                }
            }

            if(min == Integer.MAX_VALUE) sb.append("-1\n");
            else sb.append(min + " " + max + "\n");
        }
        System.out.println(sb);
    }
}

제출