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

문제

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

 

문제 개요

이 문제는 주어진 문자열에서 특정 문자가 정확히 K번 등장하는 연속 문자열의 길이를 구하는 문제입니다. 두 가지 조건에 따라 계산해야 합니다

1. 특정 문자가 정확히 K번 등장하는 가장 짧은 연속 문자열의 길이
2. 특정 문자가 정확히 K번 등장하며, 문자열의 시작과 끝 문자가 같은 가장 긴 연속 문자열의 길이

 

접근 방법

이 문제는 해시맵과 리스트를 활용한 인덱스 추적 방식으로 해결하였습니다.

1. 문자 인덱스 맵 생성
   • 문자열의 각 문자를 순회하며 해당 문자가 등장한 위치(인덱스)를 저장합니다.
   • 이를 위해 HashMap<Character, List<Integer>> 자료구조를 사용하였고, 각 문자마다 등장한 인덱스 리스트를 만들어 빠르게 참조할 수 있도록 하였습니다.
2. K번 등장하는 문자열의 길이 계산
   • 저장된 각 문자의 인덱스 리스트를 순회하며 해당 문자가 K번 이상 등장하는지 확인합니다.
   • 등장 횟수가 K번 이상인 경우, 리스트의 연속된 K개의 구간을 선택하여 문자열 길이를 계산합니다.
     • 최소 길이 계산: 연속된 K개의 구간에서 문자열의 길이를 구하고, 그중 가장 짧은 값을 저장합니다.
     • 최대 길이 계산: 동일한 방식으로 구간에서 문자열 길이를 구하고, 그중 가장 긴 값을 저장합니다.
   • 만약 어떤 문자도 조건을 만족하지 못하면 결과로 -1을 반환하도록 처리하였습니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++) {
            String s = br.readLine();
            int k = Integer.parseInt(br.readLine());

            HashMap<Character, List<Integer>> map = new HashMap<>();
            makeMap(map, s);
            isPossible(map, s, k);
        }
    }

    public static void isPossible(HashMap<Character, List<Integer>> map, String s, int k) {
        int a = Integer.MAX_VALUE;
        int b = Integer.MIN_VALUE;

        for(List<Integer> list : map.values()) {
            if(list.size() < k) continue;
            for(int i=0; i<list.size()-k+1; i++) a = Math.min(a, list.get(i+k-1) - list.get(i) + 1);
            for(int i=0; i<list.size()-k+1; i++) b = Math.max(b, list.get(i+k-1) - list.get(i) + 1);
        }

        System.out.println(a == Integer.MAX_VALUE ? -1 : a + " " + b);
    }

    public static void makeMap(HashMap<Character, List<Integer>> map, String s) {
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);

            map.putIfAbsent(c, new ArrayList<>());
            map.get(c).add(i);
        }
    }
}