[Grind75-LeetCode] Minimum Window Substring JAVA

반응형

728x90

[Grind75-LeetCode] Minimum Window Substring - Hard

---

접근

• 슬라이딩 윈도우

---

풀이

LeetCode에서 푸는 첫 Hard 문제로 Grind75에서 easy와 medium 문제는 끝이 나고 hard 난이도 문제가 시작되었다. 이 문제는 문자열 s, t가 주어지는데 문자열 t가 s안에 포함되는 가장 작은 단위의 부분 문자열을 구하는 문제이다. 문자열 t에 존재하는 문자들이 모두 포함되기만 하면 된다.

s = "ADOBECODEBANC", t = "ABC"

예제 1번으로 t의 문자가 모두 포함된 가장 짧은 길이인 "BANC"가 정답이 된다. t의 문자인 A, B, C가 모두 포함되어 있기 때문이다. 

 

문제에서 window라고 했듯이 슬라이딩 윈도우를 사용하면 O(n + m)을 만족하며 풀 수 있다. 윈도우를 늘려가며 범위에 t가 포함되는지 체크하면 된다. 

    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";

        int[] wordsCount = new int[128];

        for (char c : t.toCharArray()) {
            wordsCount[c]++;
        }
        
        int uniqueCount = 0;
        for (int count : wordsCount) {
            if (count > 0) uniqueCount++;
        }

우선 t의 길이가 s의 길이보다 짧을 경우 빈 문자열을 반환한다. 그리고 t에 있는 문자들의 등장 횟수를 저장해 주는데 map을 사용하지 않고 바로 배열을 통해 저장해 주었다. 그리고 몇 종류의 문자가 등장하는지 세어주었는데 중복된 문자의 경우도 확실하게 체크를 해야 하기에 중복 문자 체크 시 편의를 위함이다.

	int[] current = new int[128];
        int left = 0;
        int right = 0;
        
        int matchCount = 0;

        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        int minRight = 0;

 

현재 윈도우에 들어있는 문자의 개수를 셀 배열과 포인터로 사용할 변수들을 선언하고 문자가 매치되었는지 체크할 변수도 선언한다. 위에서 세었던 고유 문자의 종류 uniqueCount와 matchCount를 비교해 모든 문자가 처리되었는지 비교를 하게 된다. 그리고 부분 문자열의 최소 길이를 관리할 minLen와 결과로 반환할 부분 문자열의 시작과 끝 인덱스를 기록할 변수들을 선언한다. 

	while (right < s.length()) {
            char c = s.charAt(right);
            current[c]++;

            if (wordsCount[c] > 0 && current[c] == wordsCount[c]) {
                matchCount++;
            }

처리가 시작되고 오른쪽 포인터가 문자열 s의 길이보다 작은 경우 반복한다. current 배열에 오른쪽 포인터 문자의 개수를 증가시키고 해당 문자가 t에도 존재하고 현재 윈도우에 있는 문자의 개수와 t에 있는 문자의 개수가 같다면 matchCount를 증가시킨다. 문자열 t에 A가 3개가 있고 현재 윈도우에 A가 3개가 있다면 A에 대한 처리는 끝났다는 의미로 matchCount를 증가시키는 것이다. 

	    while (left <= right && matchCount == uniqueCount) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }

                char leftChar = s.charAt(left);
                current[leftChar]--;
                if (wordsCount[leftChar] > 0 && current[leftChar] < wordsCount[leftChar]) {
                    matchCount--;
                }
                left++;
            }

            right++;
        }

만약 현재 윈도우가 존재하고 matchCount == uniqueCount로 t의 모든 문자 처리가 끝났다면 현재 윈도우는 문제의 조건을 만족하는 것인데 만족하는 윈도우의 길이가 저장되어 있는 윈도우의 길이 보다 클 경우 최소 값이 아니므로 무시하고 짧을 경우 윈도우 길이의 최솟값과 각 시작 인덱스들을 기록하게 된다. 새로운 부분 문자열을 발견했으니 왼쪽 포인터를 증가시켜 윈도우를 이동하게 되는데 왼쪽 포인터에 있던 문자를 현재 윈도우 배열에 있는 값에서 감소를 시키고 해당 문자를 빼면서 t에 있는 문자의 수보다 작아지게 된다면 matchCount를 감소시키게 된다. 

	return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight + 1);

마지막으로 현재 최소 길이가 최댓값인 상태라면 부분 문자열을 발견하지 못한 것으로 빈 문자열을 반환하고 최댓값이 아니라면 구해진 인덱스 값을 통해 부분 문자열을 반환한다. 

---

전체 코드

class Solution {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";

        int[] wordsCount = new int[128];

        for (char c : t.toCharArray()) {
            wordsCount[c]++;
        }

        int uniqueCount = 0;
        for (int count : wordsCount) {
            if (count > 0) uniqueCount++;
        }

        int[] current = new int[128];
        int left = 0;
        int right = 0;
        
        int matchCount = 0;

        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        int minRight = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            current[c]++;

            if (wordsCount[c] > 0 && current[c] == wordsCount[c]) {
                matchCount++;
            }

            while (left <= right && matchCount == uniqueCount) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                    minRight = right;
                }

                char leftChar = s.charAt(left);
                current[leftChar]--;
                if (wordsCount[leftChar] > 0 && current[leftChar] < wordsCount[leftChar]) {
                    matchCount--;
                }
                left++;
            }

            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight + 1);
    }
}