다몽상가의 blog

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

두 문자열이 주어지고 A 문자열의 부분 연속문자열 중 B 문자열의 글자들을 포함하는 제일 짧은 문자열을 구하는 문제이다.

아이디어

문제의 포인트는 확인해야되는 문자열이 "aab" 라면 부분연속 문자열에 a가 2개이상, b가 1개 이상 포함되어야 한다는 것이다.

바로 직전 문제의 슬라이딩 윈도우 알고리즘의 기초와 관련 문제를 포스팅해두었으니 참고하면 좋을 것 같다.

매번 오른쪽 포인터를 늘리면서 판단 조건에 대해 valid 할 때 / invalid 할 때 행동을 어떻게 설정하는지가 관건이다.

백준에서는 투포인터 알고리즘과 항상 같은 카테고리에 들어있는 것 같은데 큰 범위에서 보면 슬라이딩 윈도우도 포인터를 2개를 쓰니 투 포인터라고 할 수 있는 것 같다. 다만 투 포인터 알고리즘은 두 포인터의 이동방향이 좌에서 우로 동일하지 않은 경우도 존재하니 조금은 다르다고 할 수 있겠다.

https://www.acmicpc.net/workbook/view/8977

팁으로 문자열 매칭을 하는 경우 int[256] 배열을 생성하면 대소문자, 특수문자를 포함한 ASCII 코드 기반 문자를 쉽게 카운팅할 수 있다. 

풀이

class Solution {
    public String minWindow(String s, String t) {
        int[] arr = new int[256];
        int[] pattern = new int[256];

        for (int i = 0; i < t.length(); i++){
            pattern[t.charAt(i)]++;
        }

        String answer = "";
        int len = s.length()+1;
        outer : for (int l = 0, r = 0; r < s.length(); r++){
            int c = s.charAt(r);
            arr[c]++;

            for (int i = 0; i < 256; i++){
                if (arr[i] < pattern[i]) continue outer;
            }

            if (len > r - l + 1){
                answer = s.substring(l, r+1);
                len = r-l+1;
            }

            arr[s.charAt(l++)]--;
            while(arr[s.charAt(l-1)] >= pattern[s.charAt(l-1)]){
                if (pattern[s.charAt(l)] > 0 && len > r - l + 1){
                    answer = s.substring(l, r+1);
                    len = r-l+1;
                }
                arr[s.charAt(l++)]--;
            }
        }
        return answer;
    }
    
}

후기

슬라이딩 윈도우 알고리즘도 어느정도 정형화하여 풀 수 있는 것 같다 (아닌가)

리트코드도 좋은 문제가 많으니 영어에 큰 부담이 없다면 외국계 기업에 생각이 있지 않더라도 한 번 풀어보는게 어떨까!

질문, 피드백은 언제나 환영입니다 :)

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

반복되는 글자를 가지고 있지 않는 연속되는 부분집합 중 가장 긴 부분집합의 길이를 구하는 문제이다.

아이디어

개발자 영맨 님의 유튜브 영상을 보면서 리트코드 문제도 풀어보면 좋겠다는 생각에 시작하게 되었다.

구독하면 외국 개발회사 (구글, 아마존, 메타 등) 기출 문제 및 출제 빈도를 알 수 있다.

위 문제는 슬라이딩 윈도우 알고리즘 기초문제 중 하나로 슬라이딩 윈도우의 주요 아이디어는 아래와 같다. 

시작복잡도는 O(N)이다.

1. L, R 2개의 포인터를 0에서 부터 시작
2. R은 계속 1씩 늘리고 어떠한 조건이 valid (or invalid) 할 때 L을 한 칸 씩 올림
3. R이 모든 범위를 훑을 때까지 지속

풀이

class Solution {
    public int lengthOfLongestSubstring(String s) {
		// if you want to perform pattern-matching algorithm, use int[256] to cover all UTF-8 characters
		int[] arr = new int[256];
        int answer = 0;
		// when r repeats specific times, let's use for() instead of while()
        for (int l = 0, r = 0; r < s.length(); r++){
            int c = s.charAt(r);
            arr[c]++;
            while(arr[c] > 1){
                arr[s.charAt(l++)]--;
            }
            answer = Math.max(answer, r-l+1);
        }
        return answer;
    }
}

후기

리트코드는 난이도를 Easy, Medium, Hard로만 나누기 때문에 난이도를 세부적으로 볼 수 없다는 단점이 있지만

문제에 대한 다양한 풀이를 쉽게 볼 수 있고 틀린 테스트케이스의 인풋과 결과를 볼 수 있다는 장점이 있다!  

다음 포스트도 리트코드로 가보자!

질문 피드백은 언제나 환영입니다 :)