4-4 모든 아나그램 찾기(Sliding Window, HashMap)

 

문제 링크 : https://cote.inflearn.com/contest/10/problem/04-04

** 변경 전 틀린 코드 

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        char[] arr = br.readLine().toCharArray();
        String word = br.readLine();
        Map<Character, Integer>map = new HashMap<>();
        int result=0;
        int start=0;
        int window = word.length();
        for(int i=0; i<arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
            if(i>=window-1) {
            int cnt=0;
            for(int j=0; j<word.length(); j++) {
                if(map.containsKey(word.charAt(j))) {
                    cnt++;
                }else break;
            }
            if(cnt==word.length()) {
            result++;
            System.out.println(map);
            }
            map.put(arr[start], map.getOrDefault(arr[start], 1)-1);
            if(map.get(arr[start])==0)map.remove(arr[start]);
                start++;
            }
        }
        System.out.println(result);
        br.close();
        bw.close();
    }
}
 

 

- 투포인터와 슬라이딩윈도우의 장점인 시간복잡도 O(n)도 안되고, 문제 해결 방법을 잘못 설정하였음.

- compare_word에 대한 비교 방식을 for문으로 진행하다보니, 불필요한 반복이 진행되고 방식도 틀림

- compare_word에 대한 비교방식을 어떻게 하면 효율적으로 진행할 수 있을지에 대한 생각을 잘 못한게 큼

 

** 변경 이후 코드

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String word = br.readLine();
        String word2 = br.readLine();
        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> compare_map = new HashMap<>();
        for(char a : word2.toCharArray()) {
            compare_map.put(a, compare_map.getOrDefault(a,0)+1);
        }
        int window = word2.length()-1;
        int start=0,cnt=0;
        for(int i=0; i<window; i++) {
            map.put(word.charAt(i), map.getOrDefault(word.charAt(i), 0)+1);
        }
        for(int i=window; i<word.length(); i++) {
            map.put(word.charAt(i), map.getOrDefault(word.charAt(i), 0)+1);
            if(map.equals(compare_map))cnt++;
            map.put(word.charAt(start), map.get(word.charAt(start))-1);
            if(map.get(word.charAt(start))==0)map.remove(word.charAt(start));
            start++;
        }
        System.out.println(cnt);
        // 0 0 0
        br.close();
        bw.close();
    }
}
 

 

- 비교하는 문자열을 map으로 만들고 이를 토대로 HashMap의 Equals 함수를 통해 비교를 진행

- 시간복잡도 O(n)의 슬라이딩 윈도우, 투포인터 알고리즘으로 완료