🟠[Leet code - 567] Permutation in String ✅

Permutation in String - LeetCode

문제

• Input
  문자열 s1, s2
• Output
  s1의 순열이 s2에 포함되어 있는지에 대한 bool 값
  ※ 여기서 말하는 순열은 s1의 길이와 같은 순열을 의미한다.
• Constraints
  s1, s2 모두 알파벳 소문자로 이루어져 있다.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관없음 | O(log n) : 크게  상관 없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$1 \le s1.size,  s2.size \le 10'000$이기에, $O(n^2)까지 가능하긴 하지만,
입력 데이터가 두 가지로 s1과 s2 두 문자열이 주어지지만, 핵심 탐색 대상은 s2이므로, 모든 부분 문자열을 직접 만들고 비교하면 최악의 경우 O(n^2) 이상이 될 수 있으므로, 최대한 $O(n \log n) 이하의 복잡도로 풀이하려 했다.

 

 

해결 과정

처음 문제를 보고, 간단하게 두 가지 부분 문제로 나누었다.

1. s1의 순열 구함
2. s2에서 있는지 일일이 확인함

이게 기본 흐름이라고 생각하고, 먼저 s1의 순열과 s2의 부분 문자열을 확인하는 방법에 대해 고민했다.

간단하게 사용한 알파벳마다의 개수가 같은지를 확인하면 되지 않을까라고 생각하여, 각 알파벳마다의 사용한 개수를 배열에 저장하여 배열이 같은지 확인하기로 했다.

 

해당 방법을 사용하려고 생각해 보니, 이렇게 하면 모든 순열을 구하지 않아도 됐었다.

왜냐하면 [a, b, c]나 [b, c, a]나 문자별 빈도수는 똑같기 때문이다.

 

그래서 해당 방법으로 진행하기로 했고, s1의 문자별 빈도수를 저장하고, s2를 순회하면서 확인하는 식으로 진행하려고 했다.

아래와 같은 수도 코드를 대략 작성하고 구현에 들어갔다.

arr1 = size 26 array initialized 0
arr2 = size 26 array initialized  0

// s1, s2 초기 값 저장
FOR i from 0 to s1.size
    arr1[s1[i] - 'a']++;
    arr2[s2[i] - 'a']++;

FOR (0 <= i <= s2.size - s1.size)
    arr2업데이트
    if (each(arr1.begin, arr1.end, arr2.begin) == true) return true;

return false;

해당 방법은 첫 번째 반복문 n, 두 번째 반복문 n으로 $O(n)$의 통과하기 충분한 복잡도를 가지고 있어 계속 진행하였다.

 

 

구현

기존 계획에서 추가된 것 중 하나로, 먼저 처음 부분의 예외처리인데,

문제에는 s1의 길이가 s2보다 무조건 짧다고 작성되어 있지 않기 때문에, 큰 경우에는 false로 처리를 했다.

 

그리고 s2를 순회할 때 반복문 한 번마다 계속 문자 빈도수를 계산하는 건 비효율적이기 때문이었다.

문자 빈도수는 앞과 뒤만 변경되기 때문에, 투 포인터를 이용한 슬라이딩 윈도우 알고리즘을 사용하였다

 bool checkInclusion(string s1, string s2) {

        // s1의 길이가 더 큰 경우 처리
        if (s2.size() < s1.size()) return false;

        vector<int> arr1('z'-'a' + 1, 0);
        vector<int> arr2('z'-'a' + 1, 0);

        // 각 문자열 초기 값
        for (size_t i = 0; i < s1.size(); ++i)
        {
            arr1[s1[i] - 'a']++;
            arr2[s2[i] - 'a']++;
        }

        int l = 0; int r = s1.size() - 1;
        while(true)
        {
            if (equal(arr1.begin(), arr1.end(), arr2.begin()) == true) return true;

            l++, r++;
            if (s2.size() <= r) break;

            arr2[s2[l - 1]-'a']--;
            arr2[s2[r]-'a']++;
        }

        return false;
    }

 

 

개선 코드

슬라이딩 윈도우를 좀 더 최적화한 코드다.

매번 각 배열이 같은지 확인하는 연산을, 길이 비교로 섹시하게 최적화를 해버린다.

 

해당 방법이 가능한 이유는, 윈도우의 내부를 항상 table의 문자 빈도수를 넘지 않는 상태를 만들기 때문에, 길이가 같다면 문자의 구성도 정확히 일치한다는 뜻과 일맥상통하기 때문이다.

bool checkInclusion(string s1, string s2) 
{
    vector<int> table(26, 0);
    
    for (char c: s1)
    {
        ++table[c-'a'];
    }

    int l = 0;
    for (int r = 0; r < s2.size(); ++r) 
    {
        char c = s2[r];
        --table[c-'a'];
        
        while (table[c-'a'] < 0)
        {
            ++table[s2[l++]-'a'];
        }

        if (r - l + 1 == s1.size()) return true;
    }
    
    return false;
}