꿀잠

https://leetcode.com/problems/sliding-window-maximum/description/

주어진 길이의 구간 별 max 값을 배열로 반환 해야 하는 문제이다. 최대 값이 나온 index가 허용하는 범위 내에 새로운 최대 값이 나온다면 해당 값을 기준으로 또 다시 허용하는 구간을 정하면 된다. max 값이 나온 인덱스를 관리 추적하면서 문제를 해결해 주었다. 아래와 같은 코드로 통과하였다.

import java.util.*;  
  
public class Solution {  
    public int[] maxSlidingWindow(int[] nums, int k) {  
        int[] answer = new int[nums.length - k + 1];  
  
        int max = 0;  
        int maxIdx = 0;  
        for(int i = 0; i < k; i++){  
            if(nums[i] > max){  
                max = nums[i];  
                maxIdx = i;  
            }  
        }  
  
        int ansIdx = 0;  
        answer[ansIdx++] = max;  
  
        for(int r = k; r < nums.length; r++){  
            int num = nums[r];  
            if(nums[r] >= max){  
                max = nums[r];  
                maxIdx = r;  
            }else if(r - k >= maxIdx){  
                maxIdx = r - k + 1;  
                max = nums[maxIdx];  
                for(int i = maxIdx; i <= r; i++){  
                    if(nums[i] >= max){  
                        max = nums[i];  
                        maxIdx = i;  
                    }  
                }  
            }  
  
            answer[ansIdx++] = max;  
        }  
  
        return answer;  
    }  
}

Leetcode의 경우 문제를 통과한 이후 다른 정답들과 비교해서 속도 백분율을 보여준다. 아쉽게도 속도가 나오지 않아 다른 방식들을 확인해보았다. 다른 정답의 경우 Deque 자료구조를 이용해 유효한 max 값을 차례대로 저장해주었다. 아마도 내가 풀이한 방식의 경우 max 값이 버려질 경우 다시 추적해야 하는 방법인데 반해, 해당 방식은 갱신 될 max 값을 미리 저장해서 순회의 효율이 차이 났을 것으로 보인다.

https://leetcode.com/problems/longest-repeating-character-replacement/description/

특정 구간의 문자열이 하나로만 이루어져 있을 때 가장 긴 구간을 체크하는 문제이다. 단 k 개의 개수까지 다른 문자를 허용한다.

정답을 구하기 위하여 배열을 이용하여 글자 수가 늘어나는 것을 체크해주었다. 이 때 특정 길이까지 한번 체크한 이후에는 그 길이 이상일 경우만 정답이 될 수 있다는 점을 이용해 길이 조건을 유지할 수 있다. 반복된 문자 개수와 k의 합계가 현재의 길이보다 크다면 left를 증가 시켜 길이를 체크해 주었다. 아래는 전체 통과 코드이다.

public class Solution {  
    public int characterReplacement(String s, int k) {  
        int[] current = new int[26];  
        int maxRepeat = 0;  
        int answer = 0;  
        int l = 0;  
  
        for(int r = 0; r < s.length(); r++){  
            char now = s.charAt(r);  
            current[now - 'A']++;  
            maxRepeat = Math.max(maxRepeat, current[now - 'A']);  
  
            if(r - l + 1 - maxRepeat > k){  
                current[s.charAt(l) - 'A']--;  
                l++;  
            }  
  
            answer = Math.max(r - l + 1, answer);  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/minimum-window-substring/description/

두 문자열이 주어질 때 두번째 문자열이 첫번째 문자열에 모두 포함될 수 있는 최소 길이를 찾는 문제이다.

부분 문자열을 찾기 위해 좌우측 끝을 슬라이딩 하며 찾아주었다. 이 때 문자열이 포함되는지 여부는 Map 자료구조를 이용해 주었다. 중복되는 문자도 있을 수 있으므로 Map의 Key를 문자로 하고 반복 값을 Value로 해주었다.

우측을 증가 시키며 문자열을 확인해 주었으며, 문자열이 확인된 이후에는 좌측을 증가 시켜 문자의 최소 길이를 측정해주었다. 완성된 코드는 아래와 같다.

  
import java.util.*;  
  
public class Solution {  
    public String minWindow(String s, String t) {  
  
        // t의 문자열 정보 저장  
        Map<Character, Integer> chkMap = new HashMap<>();  
        for(char c : t.toCharArray()){  
            chkMap.put(c, chkMap.getOrDefault(c, 0) + 1);  
        }  
  
        // 슬라이딩 되는 문자열 저장  
        Map<Character, Integer> curMap = new HashMap<>();  
  
        // t의 문자열의 총 개수  
        int complete = t.length();  
        // t의 문자열과 현재 슬라이딩 중인 문자열의 개수가 같은 정도  
        int maked = 0;  
        String answer = "";  
  
        // 좌측  
        int l = 0;  
        // 우측을 증가시키며 체크  
        for(int r = 0; r < s.length(); r++){  
            char right = s.charAt(r);  
            // 현재 우측 문자의 포함여부 확인  
            if(chkMap.containsKey(right)){  
                int value = chkMap.get(right);  
                int curValue = curMap.getOrDefault(right, 0) + 1;  
                curMap.put(right, curValue);  
                // 동일 문자가 나오는 경우 필요한 문자인지 체크  
                if(curValue <= value) maked++;  
            }  
  
            // 좌측 문자의 최대값 찾기  
            while(complete == maked){  
                String now = s.substring(l, r + 1);  
                answer = answer.length() == 0 || now.length() < answer.length() ? now : answer;  
  
                char left = s.charAt(l);  
                if(chkMap.containsKey(left)){  
                    int value = chkMap.get(left);  
                    int curValue = curMap.get(left) - 1;  
                    curMap.put(left, curValue);  
                    if(curValue < value) maked--;  
                }  
  
                // 우측이 고정된 상태에서 좌측을 증가시키며 체크  
                l++;  
            }  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

주어진 문자열의 부분 문자열 중 중복되는 문자가 없이 가장 긴 부분 문자열을 찾는 문제이다

.

중복되는 부분을 체크하기 위해 set을 사용하였고, 현재 체크중인 문자열을 확인하기 위해 que ue를 사용하였다. 문자를 하나 씩 set과 queue에 넣어주며 중복이 발생하였을 경우 해당 중복 문자까지 제거하고 다시 set과 queue를 이어 나갔다. 가장 큰 문자열의 크기는 set의 size를 이용해 확인하였다.

Sliding Window 문제로 되어있어 의문점이 들어 관련 솔루션을 찾아보니 set의 size가 아닌 left와 right의 인덱스를 슬라이딩 하여 문자의 길이를 해결하는 방법이 있어서 였다. 아래는 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
    public int lengthOfLongestSubstring(String s) {  
        Set<Character> set = new HashSet<>();  
        Queue<Character> que = new ArrayDeque<>();  
        int answer = 0;  
  
        for(int i = 0; i < s.length(); i++){  
            char cur = s.charAt(i);  
  
            while(set.contains(cur)){  
                set.remove(que.poll());  
            }  
  
            set.add(cur);  
            que.add(cur);  
            answer = Math.max(answer, set.size());  
        }  
  
        return answer;  
    }  
  
}