모든 아나그램 찾기(HashMap, Sliding Window, 시간복잡도 O(n))

23 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

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

입력

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

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

출력

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

예시 입력 1

bacaAacba
abc

예시 출력 1

3

해결방법

• 찾아야 하는 문자열을 맵 형태로 저장.
• 찾고있는 슬라이딩 윈도우도 맵 형태로 저장.
• a.equals(b) → object끼리도 비교 가능하니, 활용할 것.
  • 반복할 구간을 잘 정하는 것도 요령이다.
  • 이 문제에서는 2번까지만 돌고, 3번째 부터 반복 돌리는 로직 적용함.

코드

import java.util.*;

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 x : b.toCharArray()) bm.put(x, bm.getOrDefault(x, 0) + 1);
        // 찾고자 하는 문자열의 길이를 지정하여
        int L = b.length() - 1;
        // 최초 0부터 길이까지의 문자들을 맵에 저장한다. (반복 전 초기화 과정)
        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.get(a.charAt(lt)) - 1);
            // 뺄 값이 없으면 제외시킨다.
            if (am.get(a.charAt(lt)) == 0) am.remove(a.charAt(lt));
            lt++;
        }
        return answer;
    }


    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        String a = kb.next();
        String b = kb.next();
        System.out.print(T.solution(a, b));
    }
}