[백준] BOJ 20437 문자열 게임 2 (골드 5)

문제

---

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

20437: 문자열 게임2

---

해설

---

1. Info 객체 정보 : 문자의 개수, 문자의 인덱스, 해당 문자의 첫번째 Info객체 주소, 해당 문자의 다음 Info 객체 주소
2. Map에 key: 문자, value: Info 객체 형태로 저장한다.
3. 문자열에서 문자를 하나씩 확인하며 해당 문자가 현재까지 몇개 나왔는지 확인한다.
4. 가장 최근에 나온 문자의 Info를 map에 저장한다.
5. 이때, 해당 문자가 현재까지 K개 나왔다면
   현재 문자 인덱스(newInfo.idx) - 첫 문자 인덱스(newInfo.first.idx) + 1을 min, max에 갱신한다.
6. 만약, 해당 문자가 K개 이상 나왔다 (K + 1인 경우를 의미)
   그럼 newInfo.first = newInfo.first.next;를 통해 해당 문자의 첫 Info의 다음 Info를 처음으로 만들어주고 이를 기반으로 다시 min, max를 갱신한다.
   이렇게 하면 K + 1개가 되는 순간 맨 앞의 문자를 없애주어 K개를 맞출 수 있음.

---

코드 (구현)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;

public class BOJ20437 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            int K = Integer.parseInt(br.readLine());
            if (K == 1) {
                sb.append(1).append(" ").append(1).append("\n");
                continue;
            }
            Map<Character, Info> map = new HashMap<>();

            int min = Integer.MAX_VALUE;
            int max = 0;
            for (int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                Info info = map.getOrDefault(c, null);

                Info newInfo;
                if (info == null) {
                    newInfo = new Info(1, j, null, null);
                } else {
                    newInfo = new Info(info.cnt + 1, j, info.first == null ? info : info.first, null);
                    info.next = newInfo;
                }

                if (newInfo.cnt == K) {
                    int diff = (newInfo.idx - newInfo.first.idx) + 1;
                    min = Math.min(min, diff);
                    max = Math.max(max, diff);
                } else if (newInfo.cnt > K) {
                    newInfo.first = info.first.next;
                    newInfo.cnt--;
                    int diff = (newInfo.idx - newInfo.first.idx) + 1;
                    min = Math.min(min, diff);
                    max = Math.max(max, diff);
                }
                map.put(c, newInfo);
            }
            if (min == Integer.MAX_VALUE) {
                sb.append(-1).append("\n");
                continue;
            }
            sb.append(min).append(" ").append(max).append("\n");
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

class Info {
    int cnt, idx;
    Info first, next;

    public Info(int cnt, int idx, Info first, Info next) {
        this.cnt = cnt;
        this.idx = idx;
        this.first = first;
        this.next = next;
    }
}