자바 백준 16472번 문제 - 고냥이

문제출처 : https://www.acmicpc.net/problem/16472

16472번: 고냥이

 

문제 :

 

소스코드 :

import java.util.*;
class Main {
	// 투포인터 알고리즘 + 슬라이딩 윈도우 알고리즘
	public int solution(int n, char[] arr) {
		int lt = 0, dif = 0;
		int answer = Integer.MIN_VALUE;
		// 해쉬맵 이용해 현재 인식중인 알파벳과 그 알파벳의 횟수 key와 value값으로 저장
		HashMap<Character, Integer> map = new HashMap<>();
		for (int rt=0; rt<arr.length; rt++) {
			map.put(arr[rt], map.getOrDefault(arr[rt], 0) + 1);
			// 알파벳 종류가 n개를 넘길 경우 map에서 해당 알파벳 value-1
			// value가 0이 되면 해당 알파벳 아이템 삭제
			while (map.size() > n) {
				map.put(arr[lt], map.get(arr[lt]) - 1);
				if (map.get(arr[lt]) == 0) map.remove(arr[lt]);
				lt++;
			}
			// 알파벳 종류가 n개 이하면 문자열 최대길이 비교해보고 갱신
			if (map.size() <= n) {
				answer = Math.max(answer, rt-lt+1);
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String str = sc.next();
		char[] arr = str.toCharArray();
		System.out.println(T.solution(n, arr));
	}
}

 

풀이 :

투포인터 알고리즘과 슬라이딩 윈도우 알고리즘을 바탕으로 문제를 해결하였다.

알파벳에 해당하는 26개의 배열을 생성하고 문제를 푸는 대신 해쉬맵을 이용해 문제를 풀어보았다.