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

www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

 

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

public class Main {
    static List<Integer>[] list = new ArrayList[26];
    static int K;
    static int short_ans;
    static int long_ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 26; i++){
            list[i] = new ArrayList<>();
        }
        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++){
            for (int i = 0; i < 26; i++){
                list[i].clear();
            }
            String W = br.readLine();

            for (int i = 0; i < W.length(); i++){
                int alphabet = W.charAt(i) - 'a';
                list[alphabet].add(i);
            }

            K = Integer.parseInt(br.readLine());

            boolean flag = true;
            short_ans = Integer.MAX_VALUE;
            long_ans = Integer.MIN_VALUE;

            for (int i = 0; i < 26; i++){
                if (list[i].size() >= K){
                    flag = false;
                    sol(i);
                }
            }
            if (flag) {
                System.out.println(-1);
                continue;
            }
            else {
                System.out.printf("%d %d\n", short_ans, long_ans);
            }
        }
    }
    public static void sol(int index){
        List<Integer> arr = list[index];
        int start = 0;
        int end = K - 1;
        while(end < arr.size()){
            short_ans = Math.min(short_ans,arr.get(end) - arr.get(start) + 1);
            long_ans = Math.max(long_ans,arr.get(end) - arr.get(start) + 1);
            start++;
            end++;
        }
    }
}

1. 어려웠던 점:

- 처음엔 가장 짧은 연속문자열과 가장 긴 연속문자열을 구하는 함수를 나누어 만드려고 했지만,

만들다보니 같은 루프안에서 처리가 가능해, 나누게 되면 루프를 한 번 더 돌아 비효율적이라

함수 하나로 처리하게 되었다. => 먼저 로직을 글로 정리하고 코드로 구현하는 연습을 하자.

 

2. 알게된 점:

 - 삼성SDS 알고리즘 특강에서 배웠던 슬라이딩 윈도우를 사용할 수 있었다.

특강을 듣지 않았으면 많이 어려웠을 것 같은데, ('a' -'a', 'b' -'a' .. 등으로 정수 배열을 만드는 스킬 등)

특강이 많이 도움이 된 것 같다.

3. 알고리즘 풀이:

- List<Integer>의 배열 list를 먼저 생성해주어야 하는데

List[0]은 'a'의 인덱스 들의 리스트, List[1]은 'b'의 인덱스 들의 리스트.. 이런 식이다.

인덱스란 문자열에서 몇 번째 자리에 위치하냐 이다.

예를 들어, superaquatornado 라는 문자열이 있으면

List[0]은 'a'의 인덱스들의 리스트이므로, 5, 8, 13이 담기게 된다.

 

이제 다 끝났다.

문자가 K개보다 같거나 많을 때만 sol 함수를 돌린다.

모든 알파벳이 K보다 작으면 flag를 이용해 -1을 출력하게 한다.

 

sol함수는 크기를 K를 유지하며, 각 값을 계산해준다.

end - start + 1은 부분문자열의 길이가 되며, start와 end를 1씩 늘려가며 크기 K를 유지해준다.