백준 16472번 고냥이

문제

백준 16472번 고냥이 링크

풀이 방법

먼저 문제를 잘 읽어야한다. 사실 나는 처음에 문제를 잘못 읽어서 틀렸기 때문이다.
입력으로 받은 문자열 종류 최대 개수 안에서 최대 문자열 길이를 출력해야한다.

1. 알파벳 제일 최근 출현 배열 만들기

먼저 알파벳 최근 출현 배열을 만들어야한다. 그 이유는 새로 검사한 알파벳을 추가했을 때 현재 인식 중인 알파벳의 종류에는 없는 알파벳인 경우 문제에서 주어진 N을 초과하게된다. 따라서 이 경우 제일 알파벳 종류 중 1개를 제거해야하는데, 이 때 출현이 가장 오래된 알파벳을 제거할 것이기 때문에 알파벳이 나오면 해당 알파벳의 최근 출현 위치를 기록할 배열이 필요하다.
배열의 길이는 알파벳의 개수만큼 만들면 된다.int배열의 기본 값인 0으로 초기화 되면 마지막 출현 위치가 헷갈릴 수 있으므로 -1로 초기화해주었다.

2. 현재 출현 알파벳 종류를 세기 위한 Set 만들기

현재 인식 중인 알파벳의 종류를 세기 위해서 set을 사용한다.

3. 다음 알파벳을 추가했을 때 최대 알파벳 종류의 개수를 넘어가면 문자열 길이 업데이트 하기

새로운 알파벳을 검사했을 때 3가지 경우로 나뉜다.

3-1. 현재 인식가능한 알파벳에 종류에 포함되어 있지 않은데, 이 알파벳을 인식하면 최대 인식 종류 개수를 넘는 경우

1) 정답과 비교하여 최대 인식 길이를 업데이트 해준다.
2) 최종 출현 위치가 가장 낮은(일찍인) 문자를 찾아야한다. 알파벳 출현 배열에서 -1이 아닌 가장 작은 값을 찾으면 그 알파벳일 것이다.
3) 현재 인식 길이를 현재 위치 - 찾은 알파벳의 최종 출현 위치로 업데이트 한다.
4) 찾은 알파벳의 최종 출현 위치 배열에서의 값을 -1로 업데이트 한다.
5) 인식 가능한 문자 set 에서 찾은 알파벳을 제거한다.
6) 새 문자를 인식 가능한 문자 set에 넣는다.

3-2. 현재 인식가능한 알파벳에 종류에 포함되어 있지 않은데, 이 알파벳을 인식해도 최대 인식 종류 개수를 넘지 않는 경우

1) 새 문자를 인식 가능한 문자 set에 넣는다.
2) 현재 인식 가능한 문자 종류 플래그를 1 증가시킨다.
3) 현재 인식 길이를 +1 해준다.
4) 최대 인식 길이를 업데이트 해준다.

3-3. 현재 인식가능한 알파벳에 종류에 포함된 경유

1) 새 문자를 인식 가능한 문자 set에 넣는다.
2) 현재 인식 길이를 +1 해준다.
3) 최대 인식 길이를 업데이트 해준다.

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class p16472 {
    static int [] alpha;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String line = br.readLine();
        alpha = new int ['z'-'a'+1]; // 각 알파벳의 마지막 출현 위치 배열

        Arrays.fill(alpha,-1); // 마지막 출현 위치를 -1로 초기화

        // 찾기
        Set<Character> set = new HashSet<>(); // 현재 인식가능한 알파벳들을 넣어둔 집합
        int result = 1; // 정답
        int nowKind = 1; // 현재 인식하고 있는 문자열의 종류 (첫번째꺼를 넣으므로 초기값은 1)
        int nowLen = 1; // 현재 인식하고 있는 문자열의 길이 (첫번째꺼를 넣으므로 초기값은 1)

        // 첫번째 꺼 미리 넣어두기
        set.add(line.charAt(0));
        alpha[line.charAt(0)-'a'] = 0;

        for(int i=1; i<line.length(); i++){
            char next = line.charAt(i);
            //최종 출현 위치 업데이트
            if(!set.contains(next) && nowKind == n){ // 포함되어 있지 않은데 인식 가능 종류 개수를 넘으면
                result = Math.max(nowLen, result); // 최대 길이 업데이트
                char minAlpha = findMin(); // 가장 출현 위치가 낮은 문자 찾기

                nowLen = i - alpha[minAlpha - 'a']; //현재 인식 길이 업데이트
                alpha[minAlpha-'a'] = -1; // 가장 낮은 출현위치를 -1로 설정
                set.remove(minAlpha); // 인식 가능한 문자열에서 지우기

                set.add(next); //새로운 문자 인식 가능 집합에 넣기
            }else{
                if(!set.contains(next)) nowKind++; // 현재 인식 가능 종류에 없었으면
                set.add(next);
                nowLen++;
                result = Math.max(nowLen, result);
            }
            alpha[next-'a'] = i; //최종 출현 위치 업데이트
        }
        System.out.println(result);
    }

    // 가장 출현 위치가 낮은 문자를 찾는 메서드
    static char findMin() {
        int min = Integer.MAX_VALUE;
        char c = 'a'; //임시 값 ( 아무 값이나 넣어둠)
        for(int i=0 ;i<alpha.length; i++){
            if(alpha[i]!=-1 && alpha[i] < min){
                min = alpha[i];
                c = (char)('a' + i);
            }
        }
        return c;
    }
}