인프런 모든 아나그램 찾기

문자열 2개가 주어진다.
큰 문자열과 작은 문자열이 주어지는데
작은문자열의 문자 순서와 상관없이 문자들이 큰 문자 안에 들어있을경우 카운트를 올린다

예를들어
"abcbcsdQbac"라는 큰 문자열이 있고
"abc"라는 작은 문자열이 있다
이 작은 문자열은 abc, acb, bac, bca, cab, cba가 가능하다
이 작은 문자열들이 큰 문자열에 포함되어있을경우 카운트를 올린다

위의 문자열에서는 "abc","bac"총 2개가 존재하기때문에 정답은 '2'다

문제해결

해시는 값의 순서와 상관없이 저장되고 중복이 없기때문에 해시를 이용해 풀었다

abc, acb, bac...전부다 해시에 들어가면 "a","b","c"다
그리고 문자열을 잘라서 3개씩 해시에 넣은다음 작은 문자열의 해시와 큰 문자열에서 자른 해시를 비교해 같으면 카운트가 올라가게된다

먼저 작은 문자열에 대한 해시와 큰 문자열에대한 해시2개를 생성한다

그리고 작은 문자열을 쪼개서 배열로 만들고 해시에 add시킨다

값을 3개씩 집어넣어야되는데 for문에서 처음에 2개를 넣고 그 다음부터 1개를 넣기는 힘들기때문에
(가능하지만 작은 문자열의 길이가 길어질수록 번거롭다)
먼저 제일 오른쪽 끝 문자열을 제외한 나머지 앞의 문자열들을 해시에 넣는다

그리고 큰 문자열의 배열을 돌면서 제일 오른쪽의 값을 추가한다음
작은 문자열의 해시와 비교를 한다
만약 같을경우 카운트를 올린다

그 다음 왼쪽에 있던 배열에 해당하는 해시의 개수를 하나 낮추고
만약 개수가 0이라면 없는 해시이기떄문에 삭제해버린다

코드

public int solution(String s, String t) {
        HashMap<String,Integer> sHashMap = new HashMap<>();
        HashMap<String,Integer> tHashMap = new HashMap<>();

        String[] sarr = s.split("");
        String[] tarr = t.split("");

        int lt=0,rt=tarr.length-1,cnt=0;

        for(String x : tarr) {
            tHashMap.put(x,tHashMap.getOrDefault(x,0)+1);
        }

        for(int i=0; i< tarr.length-1; i++) {
            sHashMap.put(sarr[i],sHashMap.getOrDefault(sarr[i],0)+1);
        }

        for(int i = rt; i< sarr.length; i++) {
            sHashMap.put(sarr[i],sHashMap.getOrDefault(sarr[i],0)+1);
            if(tHashMap.equals(sHashMap)) {
                cnt++;
            }
            sHashMap.put(sarr[lt],sHashMap.get(sarr[lt])-1);
            if(sHashMap.get(sarr[lt]) == 0) {
                sHashMap.remove(sarr[lt]);
            }
            lt++;
        }


        return cnt;
    }

표로 살펴보면 다음과 같다
abcbcsdQbac

[0]	[1]	[2]	[3]	[4]	[5]	[6]	..
a	b	c	b	c	s	d	..
lt		rt					..

a	b	c
1	1	1

0과 1은 위에 for문을 통해 이미 해시에 넣었고
다음 for문의 시작이 rt부터 시작해 rt에 해당하는 값을 해시에 넣는다
그렇게 되면 위에처럼 해시맵에는 a,b,c가 1씩 가지고 들어가게 된다

여기서 작은 문자열의 해시와 값을 비교한 다음 lt에 해당하는 배열값을 해시에서 값을 1낮춘다
그리고 값이 0이라면 삭제해버린다
그리고 lt++을 시켜 표적을 한칸 이동시킨다
for문도 돌아서 rt가 한칸 이동하게 되고 그 다음값을 해시에 집어넣는다

[0]	[1]	[2]	[3]	[4]	[5]	[6]	..
a	b	c	b	c	s	d	..
	lt		rt				..

b	c
2	1

이렇게 계속 반복하며 작은 문자열의 해시와 비교를 한다

Keep

끈기있게 계속 시도해보고 여러가지 방법(완전탐색, 배열)을 시도해 보았다

Problem

해시에 대한 이해가 부족해 문제를 풀때 해시를 생각하지 못했다
그래서 끝내 생각하고 풀어봐도 답이 안나와서 해설을 보고 해시로 문제를 풀어야되는것을 깨달았다

Try

중복을 없앨때, 숫자나 문자의 위치가 무작위로 상관없을때, 빠르게 값을 찾아야할때 해시를 생각해보자
여러 방면으로 생각하고 하나하나 쪼개서 생각해보자