자바(백준) 16472 고냥이

오답 노트 & 새로 알게 된 점

문제에서 최대 N개의 연속된 문자열로 투 포인터에 대한 힌트를 주었다.

 

처음에 문제 접근을 할 때, possible 배열을 boolean으로 했다.

그러나 abbcc와 같은 경우 b의 개수는 2개이므로 b를 하나 없애도 결국 하나 남기 때문에,

b가 모두 없어져야 알파벳의 한 종류가 사라지게 된다.

 

그래서 boolean으로 하면 틀리게 된다!! 처음부터 int로 할껄 그랬나보다..

 

아무튼 위에서 말했듯이 b의 개수가 2개라면 0개가 되야지 한 종류의 알파벳이 사라지게 된다.

따라서 s를 움직일 때, possible의 값이 0이 되야지 cnt(종류의 개수를 나타냄)를 -1 할 수 있다.

 

또한, e를 움직이면서 possible값을 ++ 해줄 때, possible이 1이 되면 처음 나오는 알파벳으로

cnt를 늘려줘야한다.

 

여기서 중요한 점은 cnt < N일 때까지 while문을 돌린다.

만약 cnt <= N일 때까지 돌리게 된다면 새로운 종류가 나오는 그 index까지 e가 늘어나게 되므로 

끝까지 탐색을 하지 않는다.

 

따라서 cnt < N까지 탐색을 한 뒤, while문을 한개 더 사용하여 possible의 개수가 > 0 인 곳까지 e를 늘려주고

len을 구하면 된다.

 

---

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class BOJ16472 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static int N;
    static int A[];
    static int possible[] = new int[27];
    static String str;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
        str = br.readLine();
 
        pro();
    }
 
    static void pro() {
        int e = -1, len = Integer.MIN_VALUE, cnt = 0;
 
        for (int s = 0; s < str.length(); s++) {
            if(s>=1 && possible[str.charAt(s-1) - 'a'] > 0){
                possible[str.charAt(s-1) - 'a']--;
                if(possible[str.charAt(s-1) - 'a'] == 0) cnt--;
            }
 
            while (e + 1 < str.length() && cnt < N) {
                possible[str.charAt(++e) - 'a']++;
 
                if(possible[str.charAt(e) - 'a'] == 1) cnt++;
            }
 
            while(e+1 < str.length() && possible[str.charAt(e+1) - 'a'] > 0){
                possible[str.charAt(++e) - 'a']++;
            }
 
            len = Math.max(len, e - s + 1);
        }
        System.out.println(len);
    }
}