[Grind75-LeetCode] Find All Anagrams in a String JAVA

반응형

728x90

[Grind75-LeetCode] Find All Anagrams in a String - Medium

---

접근

• 슬라이딩 윈도우

---

풀이

문자열 s 내에서 애너그램 부분 문자열 p가 존재하는지 찾는 문제이다. p 문자열을 애너그램으로 만들 수 있는 s의 시작 인덱스를 모두 찾아 리스트에 담아 반환하면 된다. 단순하게 맵에 p의 문자 등장수를 담아둔 뒤 각 자리마다 반복을 통해 계산해 보니 당연하게도 시간초과가 나왔다. 그러니 이 문제는 s의 길이가 m, p의 길이가 n이라면 적어도 O(m * n)의 복잡도 보다 빠른 방법으로 해결되어야 한다. 

 

슬라이딩 윈도우 기법을 사용하면 s를 한 번의 순회로 해결이 가능하기 때문에 O(n)의 시간 복잡도로 해결이 가능하다.

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result; 
        }


        Map<Character, Integer> pMap = new HashMap<>();
        for (char c : p.toCharArray()) {
            pMap.merge(c, 1, Integer::sum);
        }

우선 입력이 비어있거나 s의 길이가 p의 길이보다 짧다면 처리가 불가능해 빈문자열을 반환한다. 그리고 p의 문자열에 있는 문자의 개수를 세어 맵에 저장한다.

	Map<Character, Integer> sMap = new HashMap<>();
        int pLen = p.length();
        int sLen = s.length();

        for (int i = 0; i < pLen; i++) {
            char c = s.charAt(i);
            sMap.merge(c, 1, Integer::sum);
        }

        if (sMap.equals(pMap)) {
            result.add(0);
        }

문자열 s의 문자들도 개수를 세어 map에 저장하는데 0번 인덱스부터 p의 길이까지만 우선 넣게 된다. 예외가 걸러진 s는 p보다 항상 크거나 같기에 p의 길이만큼을 map에 저장하여 비교하게 된다. 0번 인덱스부터 p의 길이까지 넣은 후 두 map을 비교하여 같다면 애너그램 문자열로 시작점인 0번을 리스트에 추가한다. 

	for (int i = pLen; i < sLen; i++) {
            char c = s.charAt(i);
            sMap.merge(c, 1, Integer::sum);

            char firstC = s.charAt(i - pLen);
            sMap.put(firstC, sMap.get(firstC) - 1);
            if (sMap.get(firstC) == 0) {
                sMap.remove(firstC);
            }

            if (sMap.equals(pMap)) {
                result.add(i - pLen + 1);
            }
        }

        return result;
    }

그 이후 p부터 시작해 앞 뒤로 한 칸씩 늘려가며 진행하게 된다. s의 길이가 7이고 p의 길이가 3이라면 처음에 map에 s의 2번 인덱스까지 넣은 후 비교를 수행하고 그다음부터 한 칸을 추가할 때마다 현재 범위의 맨 앞에 문자를 제거하여 p의 길이를 맞춰준다.

s.length() = 7, p.length() = 3

sMap = s[0~2] pMap = p[0~2] (p 전체)

i = 3
sMap.put(s.charAt(3)) -> s[0~3]
s.remove(s.charAt(0)) -> s[1~3]
sMap.equals(pMap) -> 다음 상태 비교

i = 4
sMap.put(s.charat(4)) -> s[1~4]
s.remove(s.charAt(1)) -> s[2~4]
sMap.equals(pMap)

s 내부를 항상 p의 길이와 같게 유지

앞 뒤로 길이를 조절하여 항상 p의 길이와 같게 유지하며 모든 인덱스에 대해 비교가 가능하고 1번의 순회로 해결이 가능한 것이다. 

슬라이딩 윈도우 기본

그러나 생각보다 더 낮은 성능을 보여 다른 코드를 살펴봤다.

---

배열 사용

제일 제출이 많고 빠른 코드를 보니 200번 메서드를 실행시켜 평균시간 조작을 하는 부분이 있었지만 그 부분을 제외해도 7ms 정도의 속도로 빠른 실행 시간을 가졌었다. map을 사용하는 대신 배열을 통해 슬라이딩 윈도우를 사용한 방법이었다.

    public static List<Integer> findAnagrams(String s, String p) {
        var ans = new ArrayList<Integer>();

        int np = p.length(), ns = s.length();
        if (np > ns) {
            return ans;
        }

        int[] map = new int[26];
        for (int i = 0; i < np; i++) {
            map[p.charAt(i) - 'a']++;
            map[s.charAt(i) - 'a']--;
        }

우선 p가 s보다 짧을 경우 처리를 수행하고 배열을 사용해 p에 존재하는 문자인 경우 값을 증가시키고 s에 존재하는 문자의 경우 값을 감소시키는 것으로 두 문자열의 개수 관리를 하나의 배열로 처리했다.

	int diffCount = 0;
        for (int diff : map) {
            if (diff > 0) {
                diffCount++;
            }
        }

        if (diffCount == 0) {
            ans.add(0);
        }

0번 인덱스의 처리를 마무리하기 위해 문자들의 빈도수를 체크하는데 만약 해당 인덱스에 들어있는 값이 0보다 크다면 현재 문자열 s의 [0~p.length]에 존재하는 문자 개수보다 p 문자열의 존재하는 개수가 더 많다는 뜻으로 애너그램을 만들 수 없다는 뜻이다. 만약 배열의 모든 인덱스의 값이 0보다 작거나 같다면 p 문자열에 있던 모든 문자를 s[0~p.length] 내에 처리가 가능하다는 뜻으로 애너그램을 만들 수 있어 0을 결과 리스트에 추가한다. sMap.equals(pMap)과 같은 과정이다.

	for (int i = 0, n = ns - np; i < n; i++) {
            if (++map[s.charAt(i) - 'a'] == 1) {
                diffCount++;
            }
            if (--map[s.charAt(i + np) - 'a'] == 0) {
                diffCount--;
            }
            if (diffCount == 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

그리고 동일하게 남은 과정에 대해 처리를 진행하게 되고 매 차례마다 diffCount가 0으로 애너그램이 만들어지면 해당 인덱스를 추가하게 된다. 

배열 사용

하나의 배열을 통해 처리하다 보니 상당히 빠른 실행 시간을 볼 수 있다.

---

전체 코드

Map 사용

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }


        Map<Character, Integer> pMap = new HashMap<>();
        for (char c : p.toCharArray()) {
            pMap.merge(c, 1, Integer::sum);
        }

        Map<Character, Integer> sMap = new HashMap<>();
        int pLen = p.length();
        int sLen = s.length();

        for (int i = 0; i < pLen; i++) {
            char c = s.charAt(i);
            sMap.merge(c, 1, Integer::sum);
        }

        if (sMap.equals(pMap)) {
            result.add(0);
        }

        for (int i = pLen; i < sLen; i++) {
            char c = s.charAt(i);
            sMap.merge(c, 1, Integer::sum);

            char firstC = s.charAt(i - pLen);
            sMap.put(firstC, sMap.get(firstC) - 1);
            if (sMap.get(firstC) == 0) {
                sMap.remove(firstC);
            }

            if (sMap.equals(pMap)) {
                result.add(i - pLen + 1);
            }
        }

        return result;
    }
}

 

배열 사용

class Solution {
    public static List<Integer> findAnagrams(String s, String p) {
        var ans = new ArrayList<Integer>();
        int np = p.length(), ns = s.length();
        if (np > ns) {
            return ans;
        }
        int[] map = new int[26];
        for (int i = 0; i < np; i++) {
            map[p.charAt(i) - 'a']++;
            map[s.charAt(i) - 'a']--;
        }
        int diffCount = 0;
        for (int diff : map) {
            if (diff > 0) {
                diffCount++;
            }
        }
        if (diffCount == 0) {
            ans.add(0);
        }
        for (int i = 0, n = ns - np; i < n; i++) {
            if (++map[s.charAt(i) - 'a'] == 1) {
                diffCount++;
            }
            if (--map[s.charAt(i + np) - 'a'] == 0) {
                diffCount--;
            }
            if (diffCount == 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}