[랜덤 마라톤] 고냥이(16472)

1. 문제 풀이 아이디어

• 이중 포인터를 사용해 알파벳 종류를 기억하며 최대 길이를 구하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String s = bufferedReader.readLine();
        int l = 0;
        int r = 0;
        Map<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(0), 1);
        int result = 1;
        while (true) {
            if (map.size() > n) {
                map.put(s.charAt(l), map.get(s.charAt(l)) - 1);
                if (map.get(s.charAt(l)) == 0)
                    map.remove(s.charAt(l));
                l++;
            } else {
                result = Math.max(result, r - l + 1);
                r++;
                if (r == s.length())
                    break;
                map.put(s.charAt(r), map.getOrDefault(s.charAt(r), 0) + 1);
            }
        }
        System.out.println(result);
        bufferedReader.close();
    }
}

3. 정리

• 두 개의 포인터 l과 r을 초기화하고, map에 첫 문자를 넣어 시작한다.

• map의 크기가 n보다 크면, l을 증가시켜 왼쪽 포인터를 이동하고, 해당 문자의 개수를 감소시키고 개수가 0이 되면 map에서 제거한다.

• map의 크기가 n보다 작거나 같으면, 현재 구간의 길이(r - l + 1)를 계산하여 최대값을 result에 저장한다. 그 후 r을 오른쪽으로 이동하고, 해당 문자를 map에 추가하거나 개수를 증가시킨다.

• r이 문자열의 끝에 도달하면 while 루프를 종료하고 최종 결과값을 출력한다.

4. 더 좋은 코드 리뷰

public class Main {
    static int N, res;
    static int[] alpha;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int len = s.length();
        res = 0;
        alpha = new int[26];
        int start = 0, end = 0, cnt = 0;
        while (end < len) {
            if (alpha[s.charAt(end) - 'a']++ == 0)
                cnt++;
            while (cnt > N && start < end) {
                if (--alpha[s.charAt(start++) - 'a'] == 0)
                    cnt--;
            }
            res = Math.max(res, end - start + 1);
            end++;
        }
        System.out.println(res);
    }
}

• 알파벳의 개수가 26개에 불과하므로, 알파벳 종류를 기억하기 위해 Map 대신 배열을 사용했다.