[백준 / JAVA] 16472번 고냥이

문제

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

접근

일단 문제에 불필요한 내용이 많은데, 문제에서 물어보는 것은 간단하다.

주어진 문자열(s)에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열을 뽑아 냈을 때, 이 문자열의 최대 길이.

가장 처음 했던 접근은 브루트 포스이다.

이중 for문으로 시작점을 잡고 N개의 알파벳이 나올 때까지 끝점을 이동해서 길이를 갱신.
하지만, 이 방법은 $100,000 * 100,000$(문자열 최대 길이의 제곱)의 실행 횟수로 시간 초과가 발생한다.

두번째 방법은 투 포인터.

시작점과 끝점 사이의 알파벳 개수를 카운팅 하면서
N보다 작거나 같으면 끝점을 늘리고,
N보다 크면 시작점을 늘림.

처음엔 알파벳 개수를 HashSet에 담아서 카운팅 했는데, 이렇게 하면 종류만 카운트 할 수 있어 문자열의 길이를 측정하는 것이 로직적으로 복잡해졌다.

디버깅에서 어려움이 있어 반례를 찾지 못했고, 결국 HashSet을 HashMap으로 변경하여 해결할 수 있었다.

풀이

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));
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int max = 0;

        int start = 0, end = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (end < s.length()) {
            char ch = s.charAt(end);
            map.put(ch, map.getOrDefault(ch, 0) + 1);

            while (map.size() > n) {
                char startChar = s.charAt(start);
                map.put(startChar, map.get(startChar) - 1);

                if (map.get(startChar) == 0) map.remove(startChar);

                start++;
            }

            max = Math.max(max, end - start + 1);
            end++;
        }

        System.out.println(max);
    }
}

정리

투 포인터를 활용하는 접근은 맞았으나, 자료구조의 사용에서 애를 좀 먹었다.
Set과 Map을 상황에 맞게 적절히 사용할 필요가 있다.