뒤죽박죽 코딩 이야기

2022년 2월 11일 금요일 - 오늘은 FLEX

오늘 올려볼 문제는 567번 Permutation in String 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아니 왜 permutation이라고 써서 헷갈리게 하냐고!!@!!@@!!

입력

사진에서도 볼 수 있듯이 String 2개가 주어진다.

풀이 및 코드

s1의 순열 중 하나가 s2에 포함되어 있는지를 판단하는 알고리즘이다.

오늘은 문제에서 permutation이라고 써서 헷갈린 것 때문에 해맨것을 제외한다면 처음부터 정답을 생각해냈다.

기본적으로 전에 풀었던 438번 문제 Find All Anagrams in a String 문제와 거의 같은 알고리즘을 쓴다.

그렇기에 설명은 여기에서 대신하겠다.

그래서 다른 풀이를 생각해봤다.

일단 누적합마다 해쉬맵에 저장한다.

이 때 해쉬맵에 현재 누적합 - k 가 존재한다면 결과값에 해당 해쉬맵에 들어있는 값을 더한다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int[] arr = new int[30];
    public boolean checkInclusion(String s1, String s2) {
        if(s2.length() < s1.length())
            return false;

        for(int i = 0; i < s1.length(); i++)
        {
            arr[s1.charAt(i) - 'a']++;
            arr[s2.charAt(i) - 'a']--;
        }

        for(int i = s1.length(); i < s2.length(); i++)
        {
            if(check())
                return true;

            arr[s2.charAt(i) - 'a']--;
            arr[s2.charAt(i - s1.length()) - 'a']++;
        }

        if(check())
            return true;

        return false;
    }

    public boolean check()
    {
        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] != 0)
                return false;
        }

        return true;
    }
}

제출 화면

오늘은 문제에 permutation이라는 말에 꽂혀서 빨리 못 풀었던 문제였다.

그래도 뜻을 이해하고 풀어서 다행이다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.