[알고리즘] 4-4 모든 아나그램 찾기 - HashMap, Sliding Window 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

강사님의 요청으로 문제를 통째로 올리지 못하는 점 양해 부탁드립니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/04-04
• 문제 설명 : S문자열에서 T문자열과 아나그램이 되는 부분 문자열의 개수를 구하는 문제

풀이

• 두개의 HashMap 사용, eqauls메서드로 아나그램인지 판단
• Sliding window 알고리즘 사용

package inflearn.hashmap_treeset;

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

//모든 아나그램 찾기
public class Main4_4 {

    public static int solution(String s, String t) {
        int answer = 0;

        Map<Character, Integer> smap = new HashMap<>();
        Map<Character, Integer> tmap = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            tmap.put(t.charAt(i), tmap.getOrDefault(t.charAt(i), 0) + 1);
        }

        for (int i = 0; i < t.length()-1; i++) {
            smap.put(s.charAt(i), smap.getOrDefault(s.charAt(i), 0) + 1);
        }

        int left = 0;
        for (int right = t.length()-1; right < s.length(); right++) {
            smap.put(s.charAt(right), smap.getOrDefault(s.charAt(right), 0) + 1);

            if (smap.equals(tmap)) {
                answer++;
            }

            smap.put(s.charAt(left), smap.get(s.charAt(left)) - 1);

            if (smap.get(s.charAt(left)) == 0) {
                smap.remove(s.charAt(left));
            }

            left++;
       }

        return answer;
    }

    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));
    }
}