[HashMap, Sliding window] 모든 아나그램 찾기 .java

설명

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.

아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

입력

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.

S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

출력

S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.

예시 입력 1 

bacaAacba
abc

예시 출력 1

3

힌트

 

출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

 

내 풀이

1. T문자열의 문자 빈도를 구하기 위해 해시맵을 만들어 저장

2. S문자열을 배열화하여 T문자열의 길이만큼 초기 윈도우를 만들어 문자 빈도 새로운 해시맵에 저장

3. S문자열 배열의 인덱스를 오른쪽으로 하나씩 이동하여 문자 빈도 해시맵에 추가하고 윈도우의 맨 처음 문자를 빈도 해쉬맵에서 하나 감소

4. 감소한 빈도가 0이면 해시맵에서 제거

 

해시맵과 윈도우 슬라이딩을 함께 구현할 수 있는 문제였다

해시맵1.equals(해시맵2)
: 두 개의 해시맵이 같은지 비교하는 함수

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();//s문자열
        char[] chars = str.toCharArray();//s문자열 -> 배열

        String find = sc.nextLine();
        HashMap<Character, Integer> fmap = new HashMap<>();
        for(char c : find.toCharArray()){//T 문자열의 한 문자씩 해시맵에 저장
            fmap.put(c,fmap.getOrDefault(c,0) + 1);
        }

        HashMap<Character, Integer> exmap = new HashMap<>();//원도우슬라이딩으로 검사할 해시맵
        for(int i = 0; i < find.length(); i++){//초기 윈도우
            exmap.put(str.charAt(i),exmap.getOrDefault(str.charAt(i),0) + 1);
        }
        
        int answer =0;
        if(fmap.equals(exmap)){//초기 윈도우 동일한지 비교
            answer++;
        }
        //문자열을 한 칸씩 오른쪽으로 이동하며 비교
        for(int i = find.length(); i < chars.length; i++){
            //새로 추가되는 문자의 빈도를 증가
            exmap.put(chars[i],exmap.getOrDefault(chars[i],0) + 1);
            //첫번째 문자 빈도 하나 감소
            exmap.put(chars[i-find.length()],exmap.getOrDefault(chars[i-find.length()],0) - 1);
            //문자의 빈도가 0이 되면 해당 문자를 해시맵에서 제거
            if(exmap.get(chars[i-find.length()]) == 0){
                exmap.remove(chars[i-find.length()]);
            }
            //동일한지 비교
            if(fmap.equals(exmap)){
                answer++;
            }
        }
        
        System.out.println(answer);


    }
}

 

 

다른 풀이

하나 추가하는 걸 for문에 넣기 위해 초기 윈도우 길이를 T-1로 설정한 점만 다르고 나머지는 동일하다

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public int solution(String a, String b){
        int answer = 0;
        HashMap<Character, Integer> am = new HashMap<>();
        HashMap<Character, Integer> bm = new HashMap<>();

        for(char c : b.toCharArray()){
            bm.put(c,bm.getOrDefault(c,0)+1);
        }

        int L = b.length()-1;//한개는 처리 안하기 위해 빼기 1
        for(int i = 0; i<L; i++){//초기
            am.put(a.charAt(i),am.getOrDefault(a.charAt(i),0)+1);
        }

        int lt = 0;
        for(int rt = L; rt <a.length(); rt++){
            am.put(a.charAt(rt),am.getOrDefault(a.charAt(rt),0)+1);//추가
            if(am.equals(bm)){//검사
                answer++;
            }
            //맨 앞 문자 빈도 하나 감소
            am.put(a.charAt(lt),am.getOrDefault(a.charAt(lt),0)-1);
            if(am.get(a.charAt(lt)) == 0){
                am.remove(a.charAt(lt));
            }
            lt++;

        }


        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        String a = sc.next();
        String b = sc.next();

        System.out.print(T.solution(a,b));

    }
}

 

 

💡💡

투 포인터에 이제 좀 익숙해져서 금방 풀었던 문제였다 익숙해지면 재밌다