LeetCode 567(Permutation in String, java)

0. 문제

https://leetcode.com/problems/permutation-in-string/

Permutation in String - LeetCode

 

 

1. 문제 설명

- 문제에서 2개의 문자열(s1, s2)이 주어진다.

- s1을 구성하는 문자의 순열 중 하나라도 s2를 구성한다면 true를 반환하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 순열을 어떻게 구할 것인지에 대해서 생각해보자.

- 만약 s1 = "ab"라면 s2에는 "ab" 또는 "ba"를 포함하고 있어야 참이다.

 

- 문자열(s2)에 순열이 존재한다는 것은 다음 2가지 조건에 부합해야 한다.

  → substring의 순서에 상관없이 substring을 구성하는 문자가 존재한다. 

  → substring을 구성하는 문자들이 띄엄띄엄 존재하는 것이 아니라, 순차적으로 존재한다. 

 

- 이 2가지 힌트에서 다음과 같은 접근을 생각할 수 있다. 

  → substring의 구성 문자가 존재하는지 확인한다 = HashMap을 사용한다.

  → substring을 구성하는 문자가 순차적으로 존재한다 = 반복문과 포인터를 이용하여 탐색한다.

 

 

b) 두 번째 접근

- 위에서 2가지 접근법을 찾아냈다.

- 즉, 각 문자열의 구성을 기록하는 HashMap을 만들고, 이 둘의 내용을 비교하여 순열의 존재 여부를 판단한다.

 

- 첫 번째 HashMap(= map1)은 s1을 구성하는 문자의 종류와 개수를 기록한다.

- 두 번째 HashMap(= map2)은 s2를 구성하는 문자의 종류와 개수를 기록한다.

- 여기서 map2에 문자를 어떻게 기록하느냐가 문제 해결의 관건이 된다.

 

 

c) 세 번째 접근

- 우선 s2를 구성하는 문자의 종류와 개수를 기록하기 위해서 for 반복문을 사용한다.

- 이때 map2에 문자를 기록하기 위해서 2개의 포인터를 사용한다.

 

- 첫 번째 포인터는 s2를 탐색하면서 문자를 map2에 기록한다. 

- 만약 첫 번째 포인터가 (s1의 길이 - 1) 이상 포인터가 이동했다면, 두 번째 포인터가 탐색을 시작한다.

 

- 두 번째 포인터의 역할은 이전에 등장한 문자를 map2에서 삭제하는 역할이다.

- 여기서 반드시 이해하고 넘어가야 할 부분은 두 번째 포인터가 움직이는 시점이다.

 

- 두 번째 포인터는 왜 첫 번째 포인터가 (s1의 길이 - 1)만큼 움직였을 때 움직이기 시작할까? 

- 그 이유는 매번 반복할 때마다 s1의 길이만큼의 문자열을 map2에 기록하고 map1과 비교하기 위해서다. 

 

- 이러한 탐색 과정은 이전 포스팅의 달리기 비유와 동일한 원리로 동작하는 것이다.

 

 

d) 네 번째 접근

- 동일한 원리지만 배열을 이용하여 푸는 방법도 존재한다.

- 알파벳 수만큼의 길이(= 26)를 갖는 정수형 배열을 2개 만든다.

- 그리고 각 문자열을 구성하는 문자의 ASCIII 값을 index로 하여금 개수를 기록한다. 

 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

a) HashMap을 사용한 방식

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        
        HashMap<Character, Integer> map1 = new HashMap<>();
        
        for(char c : s1.toCharArray()) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }
        
        HashMap<Character, Integer> map2 = new HashMap<>();
        int start = 0;
        
        for(int end = 0; end < s2.length(); end++) {
            char c = s2.charAt(end);
            map2.put(c, map2.getOrDefault(c, 0) + 1);
            
            if(end + 1 >= s1.length()) {
                if(map1.equals(map2)) {
                    return true;
                }
                
                char leftChar = s2.charAt(start++);
                
                map2.put(leftChar, map2.get(leftChar) - 1);
                if(map2.get(leftChar) == 0) {
                    map2.remove(leftChar, 0);
                }
            }
        }
        return false;
    }
}

 

 

b) 배열을 이용한 방식

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for(int i = 0; i < s1.length(); i++) {
            int idx = s1.charAt(i) - 'a';
            s1Count[idx]++;
            s2Count[idx]++;
        }
        
        int start = 0;
        int end = 0;
        
        while(end < s2.length()) {
            
            if(s2Count[s2.charAt(end) - 'a'] > 0) {
                s2Count[s2.charAt(end) - 'a']--;
                if((end - start + 1) == s1.length()) {
                    return true;
                } else {
                    end++;
                }
            } else {
                if(s1Count[s2.charAt(start) - 'a'] > 0) {
                    s2Count[s2.charAt(start) - 'a'] ++;
                    start++;
                } else {
                    end ++;
                    start = end;
                }
            }
        }
        return false;
    }
}

 

- 배열이 확실히 데이터에 접근하는 속도가 빠르기 때문에 연산 속도 또한 빠른 것을 확인할 수 있다.