[백준 16472 - Java] 고냥이

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

16472번: 고냥이

 

문제

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)

둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다. 

 

풀이

이 문제는 Queue를 이용해서 풀이하였습니다. 또한 큐에 있는 알파벳의 문자열에서의 index를 저장하기 위한 idx[26]배열을 사용했습니다.

1. 우선 idx[]를 모두 -1로 초기화해준 후 풀이를 시작합니다.
2. 문자열을 따라서 하나의 문자씩 queue에 push해줍니다.
3. 만약 해당 문자의 알파벳의 idx[]가 -1이라면 큐안에 동일한 알파벳이 없으므로 알파벳 종류 수를 증가(diff++)시켜줍니다. 
4. -1인 경우와 아닌 경우에 모두 현재 index로 idx[]값을 업데이트 합니다.
5. 만약 diff가 N보다 커졌다면 큐에서 pop해주어야 합니다.
   • 이때 pop된 객체의 index가 해당 알파벳의 idx[]의 값과 같다면 idx[]에 -1을 넣어주고 알파벳 종류 수를 감소(diff--)시키고 pop작업을 종료합니다.
   • 다르다면 해당 알파벳이 큐안에 더 존재한다는 것이므로 계속 pop하는 반복을 이어갑니다.
6. 이를 반복하면서 큐의 사이즈를 현재의 최대 길이와 비교하며 최대 길이를 업데이트해줍니다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int answer = 0;
		int N = sc.nextInt();
		int[] idx = new int[26];

		for(int i=0; i<26; i++)
			idx[i] = -1;

		String s = sc.next();

		Queue<Alphabet> q = new LinkedList<Alphabet>();
		int k = 0;
		int diff = 0;

		while(k<s.length()) {
			char c = s.charAt(k);
			q.add(new Alphabet(k, c));
			if(idx[c-'a'] == -1) {
				diff++;
			}
			idx[c-'a'] = k;


			while(diff > N) {
				Alphabet f = q.poll();
				if(f.index == idx[f.alpha-'a']) {
					idx[f.alpha-'a'] = -1;
					diff--;
					break;
				}
			}

			if(answer < q.size())
				answer = q.size();
			
			k++;

		}

		System.out.println(answer);
	}

	static class Alphabet {
		int index;
		char alpha;

		Alphabet(int index, char alpha) {
			this.index = index;
			this.alpha  = alpha;
		}
	}

}