[백준] 20437번 - 문자열 게임 2 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 문자열에 대해 특정 문자를 $K$ 개 포함하는 구간의 길이의 최솟값과 특정 문자를 $K$ 개 포함하면서 구간의 양 끝 문자가 같은 구간의 길이의 최댓값을 구하는 문제다. 각 문자의 등장 위치를 문자별로 구분해서 저장한 후 각 문자의 등장 위치들에 대한 슬라이딩 윈도우를 활용하면 해결할 수 있다.

superaquatornado 예시의 경우

• a = 5, 8, 13
• d = 14
• e = 3
• n = 12
• o = 10, 15
• p = 2
• q = 6
• r = 4, 11
• s = 0
• t = 9
• u = 1, 7

와 같이 저장한 후 각 문자별 위치들에 대해 슬라이딩 윈도우를 적용하면 된다. 이를 위해 알파벳 소문자를 인덱스와 매핑시켰다.

---

2. 코드

1. 슬라이딩 윈도우 [Java]

Java에서 제네릭 배열은 생성할 수 없어서 Raw Type의 리스트 배열로 생성이 되긴 하지만 PS에서는 크게 문제가 없어서 활용했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            char[] W = br.readLine().toCharArray();
            int K = Integer.parseInt(br.readLine());

            List<Integer>[] pos = new ArrayList[26];
            for (int i = 0; i < 26; i++) {
                pos[i] = new ArrayList<>();
            }

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

            int min = Integer.MAX_VALUE;
            int max = 0;

            // 알파벳별 리스트에 대해 슬라이딩 윈도우 수행
            for (List<Integer> list : pos) {
                for (int i = 0; i <= list.size() - K; i++) {
                    min = Math.min(min, list.get(i + K - 1) - list.get(i) + 1);
                    max = Math.max(max, list.get(i + K - 1) - list.get(i) + 1);
                }
            }

            // min 값이 갱신되지 않은 경우로 판단
            if (min == Integer.MAX_VALUE) {
                sb.append("-1\n");
            } else {
                sb.append(min).append(" ").append(max).append("\n");
            }
        }

        System.out.println(sb);
    }
}

2. 슬라이딩 윈도우 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        string s;
        int k;
        cin >> s >> k;

        vector<vector<int>> pos(26);
        for (int i = 0; i < s.size(); i++) {
            pos[s[i] - 'a'].push_back(i);
        }

        int mn = INT_MAX;
        int mx = 0;

        // 알파벳별 리스트에 대해 슬라이딩 윈도우 수행
        for (auto& v : pos) {
            for (int i = 0; i <= (int)v.size() - k; i++) {
                mn = min(mn, v[i + k - 1] - v[i] + 1);
                mx = max(mx, v[i + k - 1] - v[i] + 1);
            }
        }

        // min 값이 갱신되지 않은 경우로 판단
        if (mn == INT_MAX) {
            cout << -1 << '\n';
        } else {
            cout << mn << ' ' << mx << '\n';
        }
    }
}

---

3. 풀이 정보

1. 슬라이딩 윈도우 [Java]

언어	시간	메모리	코드 길이
Java 11	296 ms	34748 KB	1451 B

2. 슬라이딩 윈도우 [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	2156 KB	917 B

---