백준 16472 - 고냥이

Java

16472 번 - 고냥이

문제

접근 방법

투 포인터와 Map으로 해결하였다.
부분 문자열의 시작을 나타내는 s와 끝을 나타내는 e를 두어, 각 포인터를 하나씩 이동시키며 현재 s와 e사이의 알파벳의 종류가 n보다 작으면 그 길이의 최대 값을 구한다.

부분 문자열 내의 알파벳 종류의 개수는 Map의 size()를 통해 구했는데,
e가 이동 할 때마다 Map에 add 하거나 이미 있으면 그 수를 + 1 해준다.
s가 이동할 때 이전 알파벳의 수를 Map에서 그 수를 - 1해주는데, - 1한 값이 0이면 그 알파벳을 map에 제거한다.

이런 방식으로 s와 e가 이동 할 때마다, 그 사이의 부분 문자열의 알파벳의 종류의 수를 셀 수 있다.

코드

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

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = stoi(br.readLine());
    	String str = br.readLine();


    	Map<Character, Integer> map = new HashMap<Character, Integer>();
    	char[] arrC = str.toCharArray();
    	int len = str.length();

    	int	s = 0, e = 0, num, lastS = 0;
    	while(s <= e && e <= len - 1) {
			// 하나의 알파벳을 넣는다.
			// 주의할 점은 이전에 s가 이동하여 알파벳의 수를 줄였을 때,
			// e는 이동 없이 현재 위치의 알파벳을 한번 더 put이 되므로
			// 조건문을 통해 구별한다.
    		if((s!= e || e == 0) && lastS == s)
    			map.put(arrC[e], map.getOrDefault(arrC[e], 0) + 1);

			// 알파벳의 종류의 수가 N보다 작을 때
    		if(map.size() <= n) {
    			result = Math.max(result, e - s + 1);
    			e++;
    			lastS = s;
    		}
			// 알파벳의 종류의 수가 N보다 클 때
    		else {
    			num = map.get(arrC[s]) - 1;
    			if(num == 0) {
    				map.remove(arrC[s]);	// 더 이상 부분 문자열에 존재하지 않으면 제거한다.
    			}
    			else {
    				map.replace(arrC[s], num);
    			}
    			s++;	// 부분 문자열의 시작점을 이동시킨다.
    		}
    	}

    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

map.getOrDefault(key , 0)를 배울 수 있었다.

개선할 점