본문 바로가기
Leetcode

2024. Maximize the Confusion of an Exam

by Doromi 2024. 6. 17.
728x90
반응형

You are given a string answerKey which represents the answers of a student in a multiple-choice exam, where each character is either 'T' (True) or 'F' (False). You are also given an integer 'k', which represents the maximum number of changes you can make (i.e., you can flip 'T' to 'F' or 'F' to 'T').

Your goal is to maximize the length of the longest contiguous subarray containing the same answer (either all 'T's or all 'F's) after making at most 'k' changes.

 

Optimal Approach:

  • Use a sliding window technique to find the longest segment where you can have a maximum of k changes to maintain the same character throughout the segment.

 

 

  • MaxConsecutiveAnswers 함수:
    • 'T'를 기준으로 가장 긴 연속 부분 문자열을 찾고, 'F'를 기준으로 가장 긴 연속 부분 문자열을 찾습니다. 둘 중 더 큰 값을 반환합니다.
  • MaxConsecutiveChar 함수:
    • 주어진 문자열에서 'ch'가 연속으로 가장 많이 나오는 부분 문자열을 찾기 위해 슬라이딩 윈도우를 사용합니다.
    • right 포인터를 이동시키며 슬라이딩 윈도우를 확장합니다.
    • 윈도우 내의 다른 문자의 개수(changes)가 k를 초과하면, left 포인터를 이동시켜 윈도우를 줄입니다.
    • 윈도우의 길이를 계산하여 가장 큰 값을 업데이트합니다.
public class Solution {
    public int MaxConsecutiveAnswers(string answerKey, int k) {
        return Math.Max(MaxConsecutiveChar(answerKey,k,'T'),MaxConsecutiveChar(answerKey,k,'F'));
    }
    private int MaxConsecutiveChar(string answerKey, int k, char ch){
        int left = 0;
        int right = 0;
        int maxCount = 0;
        int changes = 0;

        while(right < answerKey.Length){
            if(answerKey[right] != ch){
                changes++;
            }

            while(changes > k){
                if(answerKey[left] != ch){
                    changes--;
                }
                left++;
            }
            
            maxCount = Math.Max(maxCount, right-left+1);
            right++;
        }
        return maxCount;
    }
}

 

 

MaxConsecutiveAnswers: 이 함수는 메인 함수로, answerKey와 k를 입력받아 두 가지 경우를 고려합니다. ‘T’만 연속으로 가장 길게 만드는 경우와 ‘F’만 연속으로 가장 길게 만드는 경우를 각각 확인합니다.
MaxConsecutiveChar: 특정 문자(ch)가 연속으로 가장 많이 나오도록 하기 위해 최대 k번의 변경을 사용하여 슬라이딩 윈도우를 적용합니다.

 

728x90
반응형

'Leetcode' 카테고리의 다른 글

148. Sort List  (0) 2024.06.28
24. Swap Nodes in Pairs  (0) 2024.06.24
197. Rising Temperature  (0) 2024.05.10
2634. Filter Elements from Array  (0) 2024.05.10
2665. Counter II  (0) 2024.05.10