BOJ20437 문자열 게임2 ( String ) with JAVA

 

20437번: 문자열 게임 2

 

 

◎ 문제풀이

 

문자열 안의 부분문자열 중에서 특정 문자로 시작해서 끝나는 문자열 중 해당 문자가 K개 있는 경우의 최소길이와 최대길이를 구하는 문제이다. 문자열 안의 특정문자 K개를 찾아야 하므로 반복문이 중첩될 수 밖에 없는데, 문자열의 길이는 최대 10,000이다. 그러므로 시간초과가 발생하지 않도록, 가지치기를 할 필요가 있다. 

 

 

1. 문자열 내 알파벳 별 개수 파악하기 

 

알파벳 개수를 파악하여 K개보다 작으면 반복을 하지 않는다. 

 

2. 문자열 탐색 

 

문자열 앞 부분부터 하나씩 체크한다.

체크하는 문자가 K개보다 작으면 넘어가고 K개 이상이면 해당 문자로 시작해서 끝나는 문자열을 탐색한다.

그리고 그 문자열의 해당 문자의 개수가 K개인지 확인한다. 

 

그럼 이를 코드로 확인해보자. 

 

◎ 코드

package org.example.string;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


//BOJ20437 문자열 게임2
public class String13_2 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); //테스트케이스 개수

        while(t-- > 0) {
            String str = br.readLine();
            int k = Integer.parseInt(br.readLine());

            // 문자열 안의 알파벳 개수 세기
            int[] alphabets = new int['z' - 'a' + 1];
            for (int i = 0; i < str.length(); i++) {
                alphabets[str.charAt(i) - 'a']++;
            }

            int maxValue = 0;
            int minValue = Integer.MAX_VALUE;

            // 문자열 탐색 시작
            for(int i=0;i<str.length();i++){
                char value = str.charAt(i);
                if(alphabets[value-'a'] < k) continue; // 문자열 개수가 K보다 작으면 건너뛰기 ( 가지치기 )

                // K개 이상이면 문자열 탐색
                String subStr = getSubStr(str,value,i,k);

                // 최소길이 최대길이 초기화
                if(subStr != null){
                    if(minValue > subStr.length()) minValue = subStr.length();
                    if(maxValue < subStr.length()) maxValue = subStr.length();
                }
            }

            // 결과 출력
            if(minValue != Integer.MAX_VALUE) System.out.println(minValue+ " " + maxValue);
            else System.out.println(-1);
        }


    }

    // 문자열 탐색 함수
    public static String getSubStr(String str, char target, int start, int k){
        int count = 0;
        for(int i=start;i<str.length();i++){
            if(str.charAt(i) == target) count++;
            if(count == k) { // 동일한 문자가 K개 있으면 부분문자열 반환
                return str.substring(start,i+1);
            }
        }
        return null;
    }

}