문제 이해

고양이 말 해석기가 있다.
그렇지만 이 해석기는 N개 종류 알파벳밖에 인식하지 못한다.
이 경우, 가장 길게 해석할 수 있는 문자열 길이를 구하는 문제이다.

문제 풀이

알파벳의 종류는 26개이다. 즉, 알파벳 사용 여부를 체크할 26개의 공간을 차지하는 int형 범위를 사용해도 메모리 상 큰 문제는 없을 것이라는 생각을 했다.
그렇다면 알파벳 사용 여부는 26개의 int형 배열로 처리한다고 생각하면, 길이는 어떻게 구할 수 있을까?

물론 배열에 존재하는 개수를 모두 세봐도 되겠지만, 시간을 줄이기 위해 2개의 포인터를 활용하기로 했다.
left포인터와 right 포인터가 존재하고, 2개의 포인터는 처음에는 index = 0인 위치에 존재한다. 그리고 아래와 같은 조건에서 이동한다.

1. left : Search에서 N개보다 많은 알파벳이 사용될 경우 오른쪽으로 이동한다.

2. right : Search에서 N개 이하의 알파벳이 사용될 경우 오른쪽으로 이동한다.

또한, 최대 문자열 길이는 left가 움직일 당시의 right - left값으로 계산할 수 있을 것이다.

그렇다면, N개보다 많은 알파벳이 사용되는지는 어떻게 확인할 수 있을까? 아무리 26개의 int형 배열이라해도, 매 Search마다 루프를 돌면 무조건 시간 초과가 뜰 것이다.

이는 내가 추가할 수 있는 알파벳이 arr[right], 혹은 arr[left]밖에 없다는 것으로 해결했다.

1. right이 오른쪽으로 이동할 경우 : arr[right]에 존재하는 알파벳이 추가된다. 따라서 Alphabet배열의 index가 arr[right]인 값을 1 더해준다. 만약, arr[right] = 1이라면 이전 arr[right] = 0이였다는 것이고, 새로운 알파벳이 추가되었다는 것을 의미한다.

2. left가 오른쪽으로 이동할 경우 : arr[left]에 존재하는 알파벳을 연속 문자열에서 제거한다. 즉, Alphabet배열의 index가 arr[left]인 값을 1빼준다. 만약, arr[left] = 0이라면, 원래 가지고 있던 연속 문자열에서 한 개 알파벳이 없어졌다는 의미이므로 문자열의 알파벳 개수를 하나 줄인다.

위 방법으로 최대 문자열 길이를 구하였다.

코드

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

public class Main {
	
	static int N;
	static Integer[] arr;
	static int[] alpha = new int[26];
	
	
	static void two_pointer(int size) {
		int left = 0;
		int right = 0;
		int count = 0; // 현재 고려하는 연속 문자열에서의 알파벳 개수
		int length = 0;
		
		while(right < size) {
			if(count > N) {
                // 알파벳 개수 > N
                // left 포인터 이동 & arr[left] 값 1 빼줌
				length = Math.max(length, right-left -1);
				alpha[arr[left]]--;
				if(alpha[arr[left]]==0) {
					count--;
				}
				left++;
			}
			else {
                // 알파벳 개수 <= N
                // right 포인터 이동 & arr[right] 값 1 더해줌
				alpha[arr[right]]++;
				if(alpha[arr[right]]==1) {
					count++;
				}
				right++;
			}
		}
		
		if(count <= N) {
        /*
        right이 배열 끝까지 이동했더라도 left는 아직 움직일 수 있다.
        right이 배열 끝이라는 의미는 마지막 검사 때 알파벳 개수 <= N이였다는 
        의미이다.
        
        즉, left가 오른쪽으로 이동해도 알파벳 개수는 감소만 하므로
        항상 알파벳 개수 <= N일 것이다.
        */
			length = Math.max(length, right-left);
		}
		System.out.println(length);
	}
	
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		
		String s = sc.next();
		arr= new Integer[s.length()];
		for(int i =0;i<s.length();i++) {
			arr[i] = s.charAt(i) - 'a';
		}

		two_pointer(s.length());
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과

• 2번째 줄 틀렸습니다 : right이 배열 끝까지 이동했더라도 left가 움직일 수 있다는 가능성을 배제하고 문제를 풀어 틀렸다.