[백준 Java] 16472번 고냥이

💡문제

[Gold IV] 고냥이 - 16472

문제 링크

성능 요약

메모리: 14020 KB, 시간: 108 ms

---

🤔접근법

주어진 문자열에서 "최대" N개의 알파벳의 종류를 가지는 최대 문자열의 길이를 구하는 문제

범위 체크 및 시간복잡도 예상

• 1 ≤ n ≤ 26
• 1 ≤ 문자열 길이(N) ≤ 100,000
• $O(N)$이하 가능하다.

풀이법

❌ 접근 방법. 완탐

1. 수열의 시작점을 탐색→ $O(N)$
2. 시작점으로 부터 부분 문자열에 포함되는 문자열의 종류가 S가 되는 끝점 찾기→ $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$ → 시간 초과

⭕ 접근 방법. 투포인터, 슬라이딩 윈도

1. 문자열의 구간을 보는데 start = 0, end = 0으로 두고 시작
2. 구간을 늘려가면서 구간 내의 알파벳 종류가 n개인지 확인
   1. 구간 내 알파벳의 종류가 n과 같다면 문자열의 최대 길이 갱신
   2. 만약 구간내의 알파벳의 종류의 개수가 n보다 작으면 end를 증가시켜 구간을 늘린다.
   3. 만약 구간내의 알파벳의 종류의 개수가 n보다 크거나 같다면 새로운 구간을 보기 위해서 start를 증가 후 반복→ $O(N)$
      시작점를 증가시켰으니 구간에서 알파벳의 종류의 개수를 정정해주어야한다.

+) 이 때 부분 문자열의 알파벳의 종류는 각 인덱스를 알파벳으로 하는 배열을 만든 다음 ‘a’가 추가되면 0번 인덱스 값을 증가 시키고 cnt를 증가시켰다.

그리고 ‘a’가 빠지게 되면 0번 인덱스 값을 감소 시키고 그 값이 0이라면 cnt 도 감소하였다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$

---

🤯FAIL

문제를 잘 읽자….

아래와 같은 경우 최대 5개의 알파벳종류를 사용할 수 있기 때문에 a로만 이루어진 문자열은 알파벳을 1개만 사용함으로 모두 다 번역이 가능하다 그래서 결과는 5가 나와야한다.

나는 무조건 5개만 사용하는 경우만 고려해줘서 틀렸다.

5
aaaaa

😎SUCCESS

• 생각한 시간복잡도와 로직은 맞게 판단하였다.

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_16472 {
    static int N; // 최대 서로 다른 문자 개수
    static String str; // 입력 문자열
    static int alphabet[]; // 알파벳 개수를 저장하는 배열
    static int max = Integer.MIN_VALUE; // 최대 부분 문자열 길이

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        alphabet = new int[26]; // 알파벳은 총 26개
        N = Integer.parseInt(br.readLine()); // 서로 다른 문자 개수 입력
        str = br.readLine(); // 문자열 입력

        int start = 0; // 현재 부분 문자열의 시작 인덱스
        int end = 0;   // 현재 부분 문자열의 끝 인덱스
        int cnt = 1;   // 현재 서로 다른 문자 개수

        // 초기 설정: 첫 번째 문자에 대한 정보 반영
        alphabet[str.charAt(end) - 'a']++;

        while (end < str.length()) {
            // 현재 서로 다른 문자 개수가 N 이하인 경우 최대 부분 문자열 길이 갱신
            if (cnt <= N) {
                max = Math.max(max, end - start + 1);
            }

            // end를 증가시키며 부분 문자열을 확장
            if (cnt <= N) {
                end++;
                if (end < str.length()) {
                    char currentChar = str.charAt(end);
                    if (alphabet[currentChar - 'a'] == 0) {
                        cnt++;
                    }
                    alphabet[currentChar - 'a']++;
                }
            } else { // start를 증가시켜 부분 문자열을 축소
                char startChar = str.charAt(start);
                alphabet[startChar - 'a']--;
                if (alphabet[startChar - 'a'] == 0) {
                    cnt--;
                }
                start++;
            }
        }

        // 최대 부분 문자열 길이 출력 (최대 부분 문자열 길이가 초기값 그대로이면 부분 문자열을 만들 수 없으므로 0 출력)
        System.out.println(max == Integer.MIN_VALUE ? 0 : max);
    }
}