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

련지·2024년 8월 9일

20437 백준

코딩 테스트

목록 보기

5/9

오늘의 1솔 ♬

오늘의 문제는 백준의 Gold 5 문자열 게임 2 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

알파벳 소문자로 이루어진 문자열 W가 주어진다

양의 정수 K가 주어진다

어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다

어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다

처음에 문제 이해가 안 가서 이게 뭔 말인가 했는데 핵심만 말하자면 이렇다

알파벳 소문자로 이루어진 문자열 W가 주어진다

양의 정수 K가 주어진다

아래 조건을 만족하는 W의 부분 문자열을 찾는다

어떤 문자 c를 정확히 K개를 포함한다

문자열의 첫 번째와 마지막 글자가 c여야 한다

그러한 문자열 중 최소 길이여야 한다

아래 조건을 만족하는 W의 부분 문자열을 찾는다

어떤 문자 c를 정확히 K개를 포함한다

문자열의 첫 번째와 마지막 글자가 c여야 한다

그러한 문자열 중 최대 길이여야 한다

원 문제에서는 3번 문항에 "문자열의 첫 번째와 마지막 글자가 c여야 한다"는 조건은 없지만, 어차피 문자열이 최소 길이가 되려면 이 조건이 필요하다

풀이

접근 방법

문자열의 각 문자들을 훑으며 해당 문자열과 인덱스를 HashMap에 담는다

HashMap의 key(문자열을 구성하는 문자) 에 대해 아래 과정을 반복한다
2-1. 해당 문자가 문자열 안에 K 미만 개 있다면 건너 뛴다
어떤 문자 c를 정확히 K개 포함한다는 조건에 위배되기 때문
2-2. diff(해당 문자가 K개 포함되고 해당 문자가 첫 글자, 마지막 글자인 부분 문자열의 길이) 를 구한 다음 최소/최대 문자열 길이를 갱신한다

max 가 -1이라면 갱신이 일어나지 않았다는 뜻, 가능한 경우가 없다는 뜻이므로 -1을 반환한다

HashMap

{key}: {value} 로 데이터를 저장할 수 있는 자료구조다
여기서 {key} 는 하나의 문자, {value} 는 해당 문자의 index들을 담는 ArrayList로 사용했다
한마디로

문자열을 이루는 각각의 문자에 대해 그 문자들 어떤 index들에 위치해 있는지 한 번에 접근할 수 있다

예외 처리

K가 1일 때 예외 처리가 필요하다
K가 1이라는 건 부분 문자열의 길이가 1이라는 것이기 때문에 가장 짧은 or 긴 부분 문자열의 길이는 어떻게든 1이다
그래서 K를 입력 받고 1일 경우에는 다음 테스트 케이스로 넘어가도록 continue 시켰다

코드

package a2408;

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

public class d09_bj_g5_20437_문자열_게임_2 {
    public static void main(String[] args) throws Exception{
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++){
            char[] arr = br.readLine().toCharArray();
            int K = Integer.parseInt(br.readLine());
            if(K==1){
                sb.append("1 1\n");
                continue;
            }
            HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
            for(int i=0; i<arr.length; i++){
                char c = arr[i];
                if(!map.containsKey(c)){ map.put(c, new ArrayList<>()); }
                map.get(c).add(i);
            }
            int min = 99_999;
            int max = -1;
            for(char c: map.keySet()){
                int S = map.get(c).size();
                if(S < K){ continue; }
                int gap = K-1;
                for(int i=gap; i<S; i++){
                    int diff = map.get(c).get(i) - map.get(c).get(i-gap) + 1;
                    min = Math.min(min, diff);
                    max = Math.max(max, diff);
                }
            }
            if(max == -1){ sb.append("-1\n"); }
            else{ sb.append(min).append(" ").append(max).append("\n"); }
        }
        System.out.println(sb);
    }
}