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

📖 문제

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

 

 

 

💡  풀이 방식

• 슬라이딩 윈도우

1. 입력받는 문자열 w의 알파벳 갯수를 센다.

int[] alpha = new int[26];

for(int i = 0 ; i < w.length() ; i++) {
    alpha[w.charAt(i) - 'a']++;
}

 

2. 입력받은 문자열을 돌면서 해당 문자의 갯수가 k개 이하라면 탐색을 종료한다.

if(alpha[w.charAt(i) - 'a'] < k)
    continue;

 

k개 이상이라면, 뒷 문자와 비교하며 같은 문자의 갯수를 센다.

if(w.charAt(i) == w.charAt(j))
    cnt++;

 

그리고 같은 문자가 k개가 되는 순간, 문제에서 요구하는 조건만큼의 문자를 포함하는 길이가 되었으므로

min, max 값을 갱신한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int T;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            String W = br.readLine();
            int K = Integer.parseInt(br.readLine());
            
            solve(W, K);
        }
        
        System.out.println(sb.toString());
    }
    
    private static void solve(String w, int k) {
        if(k == 1) {
            sb.append("1 1").append("\n");
            return;
        }
        
        // 알파벳 별로 개수 저장하기
        int[] alpha = new int[26];
        for(int i = 0 ; i < w.length() ; i++) {
            alpha[w.charAt(i) - 'a']++;
        }
        
        int min = Integer.MAX_VALUE; // 최소 길이
        int max = -1; // 첫 번째와 마지막 글자가 같은 가장 긴 연속 문자열의 길이
        
        for(int i = 0 ; i < w.length() ; i++) {
            // 해당 문자의 갯수가 k개 이하라면 탐색 X
            if(alpha[w.charAt(i) - 'a'] < k)
                continue;
                
            int cnt = 1;
            
            // 뒷 문자열과 비교
            for(int j = i+1 ; j < w.length() ; j++) {
                if(w.charAt(i) == w.charAt(j))
                    cnt++;
                    
                // 같은 문자의 수가 k개가 되는 순간
                if(cnt == k) {
                    min = Math.min(min, j-i+1);
                    max = Math.max(max, j-i+1);
                    break;
                }
            }
        }
        
        if(min == Integer.MAX_VALUE || max == -1) {
            sb.append("-1").append("\n");
            return;
        }
        
        sb.append(min + " " + max).append("\n");
    }
}

 

 

---

💦 어려웠던 점

- 알파벳 별로 갯수 저장할 생각을 못 함,,

- 투 포인터할 생각은 했는데 인덱스 어떻게 잡을지 생각을 못 함

 

 

🧐 새로 알게 된 내용

- 알파벳 갯수 저장해서 활용할 아이디어

- 투 포인터 이중 for문으로 사용할 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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