[JAVA]BOJ 16472, 고냥이

진짜 너무너무 어렵다.. 머리의 한계를 느낌.. 덩어리(?)채로 알파벳과 개수를 key로 저장하고 더했다 빼는데 .. 잘 안되고.. 배열을 썼는데도 이상하고.. 암튼 

 

처음(0)부터 오른쪽포인터를 하나씩 늘려, 한 글자씩 길이와 알파벳 개수를 센다(map에 저장). 알파벳 개수가 N개를 넘어갔을때(N+1), 앞(0)에서부터 한 글자씩 뺀다(왼쪽포인터 증가). 빼면서 길이 -1을 하다가 해당 알파벳 개수가 0개가 되면 map에서 지운다. map에서 지우니 알파벳 개수는 N이 될거고 다시 오른쪽을 늘려나간다.. 오른쪽이 범위를 넘었을때 끝난다. 그리고 오른쪽을 늘릴때마다 최대 길이를 계산한다.

 

글로는 어려워서 그림으로 설명을 대체한다.. 

핵심은.. 두 포인터가 각각 앞에서부터 한 글자씩 본다는 점이다.

나는 a가 3개니 (a,3)하고 냅다 더해버렸다. 그리고 처음으로 다른 순간을 또 j에 저장했다가 N번째로 다른 순간이 나오면 j를 뺐다가 또 j를 초기화하고.. 너무 어렵게 풀었다 ㅠ 그리고 돌아가지도않음.. 두 포인터를 제일 앞, 그리고 제일 뒤로 놓고도 해보고 재귀도 썼다가 막 .. 암튼 그랬다.

---

아래는 전체 코드이다.

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

public class BOJ16472 {
    public static int getMaxSubString(String str, int N){
        int right = 0, left = 0, max = 0;
        Map<Character, Integer> alphaMap = new HashMap<>();
        char rChar, lChar;

        while(right < str.length()){
            // right늘리기
            rChar = str.charAt(right);
            alphaMap.put(rChar, alphaMap.getOrDefault(rChar, 0) + 1); // getOrDefalut : key 없으면 0, 있으면 value 가져옴
            right++;

            while(alphaMap.size() > N){ // 알파벳 개수 커지면 left 늘리기
                lChar = str.charAt(left);
                alphaMap.put(lChar, alphaMap.get(lChar) - 1); // left 하나씩 감소
                if(alphaMap.get(lChar) == 0)
                    alphaMap.remove(lChar);
                left++;
            }
            max = Math.max(max, right - left); // max는 모든 경우의 수마다 계산 및 비교
        }
        return max;
    }

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

        N = Integer.parseInt(br.readLine());
        str = br.readLine();

        System.out.println(getMaxSubString(str, N));
    }
}