모든 아나그램 찾기

설명

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

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

 

입력

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

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

 

출력

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

예시 입력 1 

bacaAacba
abc

 

예시 출력 1

3

 

힌트

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

 

소스 코드 1

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

//모든 아나그램 찾기
public class Main {
    public static int solution(String S, String T) {
        int ans = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();

        //투 포인터를 쓰기위해 lt를 선언한다.
        int lt = 0;
        for (int i = 0; i < T.length(); i++) { //T전체 개수 만큼 미리 map과 map2에 S,T를저장해둔다
            map.put(S.charAt(i), map.getOrDefault(S.charAt(i), 0) + 1);
            map2.put(T.charAt(i), map2.getOrDefault(T.charAt(i), 0) + 1);
        }

        boolean tf = true; //map이 map2와 같은지 판별하기 위해 tf 선언
        for (Character key : map2.keySet()) { // map의 key를 돌며 map2와 다르면 false를 반환한다.
            if (map.get(key) != map2.get(key)) {
                tf = false;
            }
        }

        if (tf) { //만약 true였다면 ans 카운트
            ans++;
        }

        for (int rt = T.length(); rt < S.length(); rt++) {
            map.put(S.charAt(lt), map.get(S.charAt(lt)) - 1);//인덱스 lt의 값을 map에서 뺀다
            map.put(S.charAt(rt), map.getOrDefault(S.charAt(rt), 0) + 1);//인덱스 rt의 값을 추가한다.
            lt++;// lt 오른쪽으로 한 칸 밈
            tf = true;
            for (Character key : map2.keySet()) {
                if (map.get(key) != map2.get(key)) {
                    tf = false;
                }
            }
            if (tf) {
                ans++;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        String T = sc.nextLine();
        System.out.println(solution(S,T));
    }
}

 

소스 코드 2

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

//모든 아나그램 찾기 다른 풀이
public class Main {
    public static int solution(String S, String T) {
        int ans = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();

        int lt = 0;
        for (char c : T.toCharArray()) { //map2에 T의 문자들의 개수를 키,값으로 저장해둔다.
            map2.put(c, map2.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < T.length() - 1; i++) { //T전체 개수-1 만큼 미리 map에 S를 저장해둔다.
            map.put(S.charAt(i), map.getOrDefault(S.charAt(i), 0) + 1);
        }

        for (int rt = T.length() - 1; rt < S.length(); rt++) {
            map.put(S.charAt(rt), map.getOrDefault(S.charAt(rt), 0) + 1); //인덱스 rt값을 map에 추가해준다.
            if (map.equals(map2)) { //map과 map2의 키,값이 모두 동일하다면 ans 카운트
                ans++;
            }
            if (map.get(S.charAt(lt)) >= 2) { //2이상이라면 삭제하면 2개가 사라지는 것이므로 1개만 줄인다.
                map.put(S.charAt(lt), map.get(S.charAt(lt)) - 1);
            } else { //1이라면 삭제, 1이하라면 존재가 불가
                map.remove(S.charAt(lt));
            }
            lt++;//lt를 오른쪽으로 한칸 민다.

        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        String T = sc.nextLine();
        System.out.println(solution(S,T));
    }
}

 

 

HashMap을 비교할 때 계속 == 또는 !=로 비교했었는데

HashMap을 비교할 때는 equals를 써야 한다고한다.

equals 사용시 내용을 비교 해주므로 해쉬맵 안의 키,값 모두 비교해준다고 한다.