[인프런 알고리즘] Chpater 4, 4번 문제(모든 아나그램 찾기)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class sec04_04 {
    public static int solution(String S, String T) {
        int count = 0;
        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> tMap = new HashMap<>();

        for (char c : T.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1); //T를 관리하는 맵 초기화
        for (int i = 0; i < T.length() - 1; ++i) sMap.put(S.charAt(i), sMap.getOrDefault(S.charAt(i), 0) + 1); //S를 관리하는 맵 초기화

        int lPtr = 0;
        for (int rPtr = T.length() - 1; rPtr < S.length(); ++rPtr)
        {
            sMap.put(S.charAt(rPtr), sMap.getOrDefault(S.charAt(rPtr), 0) + 1);
            if (sMap.equals(tMap)) ++count;
            sMap.put(S.charAt(lPtr), sMap.get(S.charAt(lPtr)) - 1);
            if (sMap.get(S.charAt(lPtr)) == 0) sMap.remove(S.charAt(lPtr));
            ++lPtr;
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();
        System.out.println(solution(S, T));
    }
}

 

설명

• 해시맵 초기화
  -> tMap: 문자열 T의 각 문자 빈도수를 저장.
  -> sMap: 초기 슬라이딩 윈도우에 해당하는 S의 첫 T.length() - 1 만큼의 문자 빈도수를 저장.
  
  
• 슬라이딩 윈도우 설정
  -> lPtr과 rPtr 두 개의 포인터를 사용하여 윈도우를 이동시키면서 S의 각 부분 문자열을 탐색한다.
  -> rPtr이 가리키는 문자를 sMap에 추가하고, lPtr이 가리키는 문자의 빈도수를 감소시키며 윈도우를 한 칸 오른쪽으로 이동한다.
  -> sMap과 tMap이 동일한지 비교하여, 같으면 애너그램이므로 count를 증가시킨다.
  
  
• 마지막으로 애너그램의 수를 의미하는 count를 반환한다.