모든 아나그램 찾기(해쉬, 슬라이딩 윈도우, 투포인터)

요약 map1.equals(map2); 로 해쉬맵들 비교 가능하다..

 

아나그램을 찾는 문제, S문자열과 찾을 T문자열을 주면 S문자열에서 부분문자열로 S 문자열을 몇번 만들수 있는지 

구하자, 아래의 경우에는 3번 가능 

bacaAacba
abc

 

내 풀이, HashMap 1개만으로 풀려고 해서 먼저 정답 문자열을 해쉬맵에 넣고 부분문자열을 정답 문자열 길이만큼 빼면서

size가 같으면서 map.get 을 했을때 갯수가 0이면 일치하다고 생각해서 풀어봤는데 케이스를 부분적으로만  통과해 실패..

 

import java.util.*;
public class Main {

    public int Solution(char[] arr1, char[] arr2){
        int k = arr2.length;
        int cnt = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        //먼저 정답이 될 배열을 넣어둠
        for(int i = 0; i < k; i++) map.put(arr2[i],map.getOrDefault(arr2[i],0)+1);
        //맵의 크기 저장
        int size = map.size();

        for(int i =0; i < k-1; i++){
            map.put(arr1[i],map.getOrDefault(arr1[i],0)-1);
        }

        int lt = 0;
        for(int rt = k-1; rt < k; rt++){
            map.put(arr2[rt],map.getOrDefault(arr2[rt],0)-1);
            for(char x : map.keySet()){
                if(map.size() == size && map.get(x) == 0) cnt++;
            }
            map.put(arr2[lt],map.get(arr2[lt])+1);
            if(map.get(arr2[lt]) == 0) map.remove(arr2[lt]);
            lt++; // lt 전진
        }
        return cnt;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String s1 = in.next();
        char[] arr1 = s1.toCharArray();
        String s2 = in.next();
        char[] arr2 = s2.toCharArray();


        System.out.print(T.Solution(arr1,arr2));
    }
}

 

강의 풀이

equals 메서드를 이용해서 map이 일치하는지 판별하는걸로 풀었다..

 

import java.util.*;
public class Main {

    public int Solution(String s1, String s2){
        int k = s2.length()-1;
        int cnt = 0;
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> ans = new HashMap<>();
        //먼저 정답이 될 배열을 넣어둠
        for(char x : s2.toCharArray()) ans.put(x,ans.getOrDefault(x,0)+1);

        for(int i =0; i < k; i++){
            map1.put(s1.charAt(i),map1.getOrDefault(s1.charAt(i),0)+1);
        }

        int lt = 0;
        for(int rt = k; rt < s1.length(); rt++){
            map1.put(s1.charAt(rt),map1.getOrDefault(s1.charAt(rt),0)+1);
            if(map1.equals(ans)) cnt++;
            map1.put(s1.charAt(lt),map1.get(s1.charAt(lt))-1);
            if(map1.get(s1.charAt(lt)) == 0) map1.remove(s1.charAt(lt));
            lt++; // lt 전진
        }
        return cnt;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String s1 = in.next();
        String s2 = in.next();


        System.out.print(T.Solution(s1,s2));
    }
}