[LeetCode] 2024 - Maximize the Confusion of an Exam(java)

https://leetcode.com/problems/maximize-the-confusion-of-an-exam/

Maximize the Confusion of an Exam - LeetCode

오늘도 어제와 같은 윈도우 슬라이딩 문제이다. 리트코드 문제를 보면 같은 유형이 연속으로 나오는 경우가 많은 것 같다.

아무튼 이번 문제도 간단하다. 

 

 

핵심

앞서 말했듯이 이번 문제도 윈도우 슬라이딩 문제이다. 

아이디어는 다음과 같다. 현재 나온 T, F의 카운트 중 작은 값을 K와 비교한다.

만약 K보다 작으면 전부다 바꿀 수 있기에 그대로 진행한다.

반대로 만약 K보다 크다면 맨 왼쪽의 윈도우 사이즈를 증가시킨다.

 

 

정답 코드

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int max = 0;
        HashMap<Character, Integer> count = new HashMap<>();

        int left = 0;
        for (int right = 0; right < answerKey.length(); right++) {
            char now = answerKey.charAt(right);
            count.put(now, count.getOrDefault(now, 0) + 1);

            while (Math.min(count.getOrDefault('T', 0), count.getOrDefault('F', 0)) > k) {
                count.put(answerKey.charAt(left), count.get(answerKey.charAt(left)) - 1);
                left++;
            }
            max = Math.max(max, right -left + 1);
        }

        return max;
    }
}

해설

로직 자체는 핵심에서 말한 부분이 전부이다.

현재 나온 문자의 카운트를 저장하기위해 Map을 사용하였다.

이제 현재(right)의 문자를 count에 넣어서 증가시킨다.

이후 만약 각 문자의 최소 count가 k보다 클 경우 제일 왼쪽(left)의 문자 count를 감소시키고 left를 증가시킨다.

이후 max값을 최신화 해준다.

 

 

다른 풀이

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        int max = 0;
        Map<Character, Integer> count = new HashMap<>();
        
        for (int right = 0; right < answerKey.length(); right++) {
            count.put(answerKey.charAt(right), count.getOrDefault(answerKey.charAt(right), 0) + 1);
            int min = Math.min(count.getOrDefault('T', 0), count.getOrDefault('F', 0));
            
            if (min <= k) {
                max++;
            } else {
                count.put(answerKey.charAt(right - max), count.get(answerKey.charAt(right - max)) - 1);
            }
        }

        return max;
    }
}

해설

이전 코드는 실제로 left를 당기고 최대 길이를 계속 확인하는 방법이었다.

이 코드는 O(n)으로 풀 수 있는 코드이다.

현재의 윈도우가 올바르다면 -> min값이 k보다 작다면, 카운트를 증가시킨다.

반대로 k보다 크다면 제일 왼쪽의 카운트를 감소시킨다.

 

 

배운 점

처음 풀이는 쉽게 생각해 낼 수 있었다.

이미 윈도우 슬라이딩을 몇 번 풀어보니 쉽게 감을 익힐 수 있었다.

하지만 두 번째 풀이는 이해하는데 오래 걸렸다. 

이게 정말 제대로 작동하는지 손으로 그려가면서 검증해 나갔다.

문제를 맞히는 것도 중요하지만 더 좋은 코드가 무엇일지 고민하는 것도 중요하다