(백준) 20437 - 문자열 게임 2 [java]

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

 

🐢 설명

하나의 문자열에 대해서 두가지 조건에 부합하는 문자열의 길이를 구하는 문제이다.

일단 첫번째 조건이 부합하지 않으면 2번째 조건도 부합하지 않으므로 첫번째 조건만 확인해서 -1을 출력할지 값을 출력할지 해주면된다.

 

조건을 체크하는 방법

• 먼저 문자열 전체를 순회하면서 알파벳 별로 등장한 인덱스를 담아준다.
• 각 알파벳 리스트를 확인하면서 크기가 조건에서 제시한 개수보다 많다면 확인해준다.
• 확인할 때는 슬라이드 윈도우 방식으로 확인한다.

슬라이드 윈도우 방식

• 인덱스를 left, right 값으로 갖게하고 right 값을 증가시킨다
• right - left + 1이 K (특정 알파벳이 포함된 개수) 라면 그때의 값을 최소값과 최대값으로 갱신시킨다
• K 이상이라면 미만이 될 때까지 left 값을 증가시킨다.

 

🐢코드

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

public class Main {
    static int T;
    static ArrayList<Integer>[] alhpa = new ArrayList[26];
    static String s;
    static int n, Min, Max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            init(br);
            search();
            if (Min == 10001) answer.append(-1).append("\n");
            else {
                answer.append(Min).append(" ").append(Max).append("\n");
            }
        }
        System.out.print(answer);
    }

    private static void search() {
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            alhpa[c - 'a'].add(i);
        }

        for (int i = 0; i < 26; i++) {
            if (alhpa[i].size() >= n) {
                twoPointer(i);
            }
        }
    }

    private static void twoPointer(int i) {
        ArrayList<Integer> list = alhpa[i];
        int left = 0;
        int right = 0;

        while (right < list.size()) {
            if (right - left + 1 == n) {
                Min = Math.min(Min, list.get(right) - list.get(left) + 1);
                Max = Math.max(Max, list.get(right) - list.get(left) + 1);
            }
            right++;
            while (right - left + 1 > n) left++;
        }
    }

    private static void init(BufferedReader br) throws IOException {
        for (int i = 0; i < 26; i++) {
            alhpa[i] = new ArrayList<>();
        }
        s = br.readLine();
        n = Integer.parseInt(br.readLine());
        Min = 10001;
        Max = 0;
    }
}

🐢 마무리

문자 별로 리스트를 만들어서 인덱스를 담는 방식을 생각하는게 주요 포인트 였다.