[LeetCode] 438번 문제를 풀어보았다. (ft. java)

2022년 2월 02일 수요일 - 휴일이 끝나간다... 흑흑

오늘 올려볼 문제는 438번 Find All Anagrams in a String 이라는 문제이다.

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

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

leetcode 편하고 좋네요

입력 예제

사진에서도 볼 수 있듯이 string 2개를 입력받는다.

---

풀이 및 코드

p라는 string을 anagram으로 갖는 s의 substring의 시작 인덱스를 찾는 문제다.

처음에는 p의 아스키코드들을 모두 더해서 s의 substring의 아스키코드 합과 같은지 비교하려했다.

하지만 abc의 값과 bbb의 값이 같은 반례를 찾아서 다른 방법을 찾았다.

그래서 생각한 방법은 각 알파벳들의 개수를 저장하는 배열을 만들고 sliding window 방식으로 접근했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int[] arr = new int[30];

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

        // p의 길이가 더 긴 경우 빈 리스트 리턴
        if(p.length() > s.length())
            return result;

        // p의 알파벳 개수를 저장하는 과정
        for(int i = 0; i < p.length(); i++)
        {
            arr[p.charAt(i) - 'a']++;
        }

        // p의 길이
        int length = p.length();

        // sliding window 방식을 사용하기 위한 초기화 과정 (p의 길이만큼 s의 substring을 추출하고 배열에 반영하는 과정(실제로 추출하는 것은 아님))
        for(int i = 0; i < length; i++)
        {
            arr[s.charAt(i) - 'a']--;
        }

        // 해당 substring이 anagram인지 판단, sliding window 방식을 사용해 substring을 하나씩 옆으로 옮김
        for(int i = length; i < s.length(); i++)
        {
            if(check())
                result.add(i - length);
            arr[s.charAt(i) - 'a']--;
            arr[s.charAt(i - length) - 'a']++;
        }

        if(check())
            result.add(s.length() - length);

        return result;
    }

    // anagram 인지 판단하는 메소드, 배열의 값이 모두 0이라면 true 아니라면 false 리턴
    public boolean check()
    {
        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] != 0)
                return false;
        }

        return true;
    }
}

---

제출 화면

오늘은 휴일인 기념과 맨날 집에서 게임만 하는 것 같아서 어느정도 생산적인 인간이 되고자 블로그를 쓰고 있다.

사실 leetcode는 백준에 비해 solution에 대한 것도 잘 되어 있어서 블로그를 쓰는 것이 큰 의미가 없다고 생각하지만 그래도 적으면 나에게 도움이 될 것이라고 생각한다.

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