[BaekJoon] 16472 고냥이 (Java)

1.  문제 링크

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

2.  문제

요약

• 베타버전의 고양이말 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못합니다.
• 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 26보다 작거나 같은 인식할 수 있는 알파벳의 종류의 최대 개수 N이 주어지고 두 번째 줄에는 문자열의 길이가 1보다 크거나 같고 100,000보다 작거나 같은 문자열이 주어집니다. 문자열에는 알파벳 소문자만 포함되어 있습니다.
• 출력: 첫 번째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static char[] alphabets;
	static int[] count;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		alphabets = scanner.nextLine().toCharArray();
		count = new int[26];
	}
	
	static void solution() {
		int ans = 1, cnt = 1;
		HashSet<Character> kinds = new HashSet<>();
		count[alphabets[0] - 'a']++;
		kinds.add(alphabets[0]);
		for(int L = 0, R = 0; L < alphabets.length; L++) {
			while(R + 1 < alphabets.length) {
				if(!kinds.contains(alphabets[R + 1])) {
					if(cnt + 1 >= (N + 1)) break;
					kinds.add(alphabets[R + 1]);
					count[alphabets[R + 1] - 'a']++;
					cnt++;
				} else {
					count[alphabets[R + 1] - 'a']++;
				}
				R++;
			}
			ans = Math.max(ans, R - L + 1);
			count[alphabets[L] - 'a']--;
			if(count[alphabets[L] - 'a'] == 0) {
				kinds.remove(alphabets[L]);
				cnt--;
			}
		}
		System.out.println(ans);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			return str;
		}
	}
}

4.  접근

• 이 문제는 투포인터를 이용하여 구할 수 있는 문제입니다.

  인식할 수 있는 문자열의 시작 부분을 고정시켜놓고 한 문자씩 추가해보면서 해당 문자를 추가했을 때 인식할 수 있는 알파벳의 종류의 최대 개수 N을 넘는지 확인하고 넘지 않는다면 다음 문자를 추가하고 넘는다면 시작 부분을 한 칸 미룬 후에 다음 문자들을 추가해보면서 인식할 수 있는 문자열을 찾습니다.

• 그 중 가장 길이가 긴 문자열의 길이를 출력합니다.
  
  
• 각 문자가 우리가 잡은 문자열에서 몇 번 나왔는지를 나타내는 1차원 배열 count를 생성하고 인식할 수 있는 문자열의 최대 길이를 나타내는 변수 ans와 우리가 잡은 문자열에 포함되어 있는 알파벳의 종류의 개수를 나타내는 변수 cnt를 생성하며 ans와 cnt는 값을 1로 초기화합니다.
• 우리가 잡은 문자열에 포함되어 있는 알파벳들을 담을 HashSet을 하나 생성하고 주어진 문자열의 첫 번째 알파벳을 HashSet에 담으며 count 배열에서 해당 알파벳 위치의 값을 1 증가시킵니다.
  • 첫 번째 알파벳을 먼저 선택하고 가기 때문에 위에서 ans와 cnt의 값을 1로 초기화하였습니다.
• 왼쪽 포인터와 오른쪽 포인터를 나타내는 L, R 변수를 0으로 초기화하고 L이 주어진 문자열 끝까지 올 때까지 투포인터 알고리즘을 통해 가장 길이가 긴 문자열의 길이를 찾습니다.
  • 오른쪽 포인터가 주어진 문자열의 끝에서 두 번째 문자까지 오기 전까지 오른쪽 포인터를 오른쪽으로 움직여보면서 해당 알파벳을 추가할 수 있는지 확인합니다.
    • 만약 오른쪽 포인터가 위치하고 있는 곳의 알파벳이 아직 우리가 잡은 문자열에 포함되어 있지 않다면 그 알파벳을 추가하였을 때 알파벳 종류의 개수 cnt가 N을 넘는지 확인하고 그렇다면 왼쪽 포인터를 이동하기 위해 while문을 빠져나가고 그렇지 않다면 HashSet에 그 알파벳을 집어넣고 그 알파벳 위치의 count 값을 1 올려준 후에 알파벳 종류가 하나 늘었기 때문에 cnt 값을 1 중가시킵니다.
    • 만약 오른쪽 포인터가 위치하고 있는 곳의 알파벳이 우리가 잡은 문자열에 포함되어 있다면 그 알파벳 위치의 count 값만 1 올려줍니다.
    • while문을 빠져나가지 않았다면 R을 1 증가시켜 문자열의 다음 알파벳을 포함하여 잡은 문자열이 인식 가능한 문자열인지 확인합니다.
  • while문이 끝났다면 현재 L이 위치한 곳에서 인식할 수 있는 문자열의 최대 길이까지 온 것이므로 ans를 갱신하고 L을 하나 움직일 것이기 때문에 현재 L 위치에 있는 알파벳은 우리가 잡을 문자열에서 개수가 하나 줄어드므로 그 알파벳 위치의 count 값을 1 줄여줍니다.
    • 만약 그 알파벳 위치의 count값을 1 줄였을 때 count 값이 0이 된다면 우리가 잡은 문자열에서 그 알파벳은 존재하지 않는다는 뜻이 되므로 kinds에서 해당 알파벳을 제거하고 cnt를 1 감소시킵니다.