[JAVA] 백준 20437 문자열 게임

20437

구현 문제인 것 같다.

문제에 나온대로 구현만 해주면 된다.

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

알고리즘

알고리즘은 다음의 순서대로 동작한다.

1. 입력 문자열의 알파벳 카운트

int[] c = new int[26];
for(char v : value){
    c[v - 'a']++;
}

• 먼저, 입력값의 문자열의 알파벳들을 카운트해준다.
• 이후에, 문자열을 반복할때 K보다 작은 카운트를 가진 값들은 연산하지 않는다.

2.

for(int i=0; i<value.length; i++){
    char now = value[i];
    if(c[now - 'a'] < K) continue;

    int count = 1;
    for(int j=i+1; j<value.length; j++){
        if(value[j] == value[i]) count++;
        if(count == K){
            if(value[i] == value[j]) max = Math.max(max, j-i+1);
            min = Math.min(min, j-i+1);
            break;
        }
    }
}

• 입력 문자 배열의 길이만큼 반복한다.
  • 앞에서 카운트한 값이, K보다 작다면 다음 반복을 돈다.
  • i+1부터, 문자 배열의 마지막까지 반복한다.
    • 만약, value[j]의 값이 value[i]와 같다면, 갯수를 카운트해준다.
    • 만약 count가 K와 같아진다면 2가지 작업을 수행하고 for문을 탈출한다.
      1. 첫번째 문자와 마지막 문자 즉, value[i] == value[j]라면, max값을 갱신한다.
      2. 최솟값을 갱신한다.

결과적으로 min, max값이 답이되고, 만약 초기값과 같다면 -1을 출력한다.

예시

---

입력값
abaaaba
3

• a : 5
• b : 2

0번 인덱스에서, a는 K보다 크기때문에 반복을 시작한다.

• j는 b, a, a까지 반복하고 이때 a의 수가 K기 때문에 반복을 종료한다.
  • min = 4, max = 4으로 갱신된다. (value[i] == value[j])

1번 인덱스에서, b는 K보다 작기 때문에 반복을 넘어간다.

2번 인덱스에서, a는 K보다 크기 때문에 반복을 시작한다.

• j는 a, a까지 반복한다.
  • min = 3, max는 갱신되지 않는다.

3번 인덱스에서, a는 반복을 시작한다.

• j는 a, b, a까지 반복한다.
  • min과 max는 갱신되지 않는다.

…

결과적으로 답은 3, 4가 된다.

소스코드

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for(int t=0; t<T; t++){
            char[] value = br.readLine().toCharArray();
            int K = Integer.parseInt(br.readLine());

            if(K == 1){
                sb.append("1 1\n");
                continue;
            }

            int[] c = new int[26];
            for(char v : value){
                c[v - 'a']++;
            }

            int min = 10_001;
            int max = 0;

            for(int i=0; i<value.length; i++){
                char now = value[i];
                if(c[now - 'a'] < K) continue;

                int count = 1;
                for(int j=i+1; j<value.length; j++){
                    if(value[j] == value[i]) count++;
                    if(count == K){
                        if(value[i] == value[j]) max = Math.max(max, j-i+1);
                        min = Math.min(min, j-i+1);
                        break;
                    }
                }
            }
            if(min == 10_001 || max == 0){
                sb.append("-1\n");
                continue;
            }
            sb.append(String.format("%d %d\n", min, max));
        }

        System.out.println(sb);
    }
}