[백준]20437: 문자열 게임 2 - JAVA

[백준]20437: 문자열 게임 2

20437번: 문자열 게임 2

풀이

🪑 처음 보자마자 굉장히 쉬운 문제라고 생각 했었엇었섯다. 투포인터를 사용하여 구현했었다.

그런데 시간초과가 발생했고,, 아무리 생각해도 다른 방법이 떠오르질 않아 다른 분의 풀이를 참고하였다.

 

🙋‍♀️ 풀이를 보고 나니,,흠,, 뭔가 시간복잡도는 투포인터를 사용하는 방식과 큰 차이가 없어 보여서 더 의아해지긴 했다. 그래도 알파벳 별로 개수를 입력받는다 라는 큰 힌트를 얻어 다시 풀어 보았다!

 

📝 문제의 조건을 정리해 보자!

• 소문자로 이루어진 문자열에서 어떤 문자를 K개 포함하는 가장 짧은, 가장 긴 문자열의 길이를 구한다.
• 만족하는 문자열이 없다면 -1을 출력한다.

 

 

🔧 문제를 풀어 보자!

1. 입력받는 문자열의 소문자별로 개수를 세 준다.
2. 문자열의 첫 번째 문자부터 탐색을 시작하며, 해당 문자의 개수가 K개 이라하면 탐색하지 않는다.
3. 뒷 문자열과 비교하여 같은 문자의 개수를 세어주고, 같은 문자의 수가 K개가 되는 순간 min, max값을 계산한다.

 

🔹 입력받는 문자열의 알파벳 개수를 센다.

- K개 이하인 문자는 탐색에서 제외하기 위함이다.

 

🔹 문자열의 첫 번째 문자부터 탐색을 하며, 해당 문자의 개수가 K개 이라하면 탐색하지 않는다.

- 탐색은 문자열의 길이 만큼 진행된다.

 

🔹 뒷 문자열과 비교하여 같은 문자의 개수를 세어주고, 같은 문자의 수가 K개가 되는 순간 min, max값을 계산한다.

- count가 K가 된다는 의미는 탐색을 시작하는 문자에서 부터 현 문자 까지 문제에서 요구하는 조건 만큼의 문자를 포함하는 길이가 되었으므로 min, max를 계산해 준다.

- min은 최소 길이 이므로 K만큼 포함되는 순간 더 이상 탐색을 할 필요가 없다.

- max는 첫 번째와 마지막 글자가 같은 가장 긴 연속 문자열의 길이이므로 K 이상 되는 순간 탐색 할 필요가 없다.

 

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int t = Integer.parseInt(bf.readLine());
        for(int i = 0; i < t; i++) {
            String str = bf.readLine();
            int k = Integer.parseInt(bf.readLine()); 
            //입력 끝
 
            if(k == 1) { //k가 1일때
                System.out.println("1 1");
                continue;
            }
 
            int[] alpha = new int[26];//알파벳 별 개수를 저장한다. 
            for(int j = 0; j < str.length(); j++) {
                alpha[str.charAt(j) - 'a']++;
            }
 
            int min = Integer.MAX_VALUE;
            int max = -1;
            for(int j = 0; j < str.length(); j++) {
                if(alpha[str.charAt(j) - 'a'] < k) continue;
 
                int count = 1;
                for(int l = j + 1; l < str.length(); l++) {
                    if(str.charAt(j) == str.charAt(l)) count++;
                    if(count == k) {
                        min = Math.min(min, l - j + 1);
                        max = Math.max(max, l - j + 1);
                        break;
                    }
                }
            }
            if(min == Integer.MAX_VALUE || max == -1) System.out.println("-1");
            else System.out.println(min + " " + max);
        }
    }        
}