[인프런 코테] 4-4 모든 아나그램 찾기 - HashMap, Sliding Window

설명

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

 

입력

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

 

출력

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

 

예시 입력 1

bacaAacba

abc

 

예시 출력 1

3

 

나의 풀이

강사님의 풀이는 처음에 부분 문자열의 길이 - 1개 만큼 map에 세팅해줬는데, 부분 문자열의 길이의 개수만큼 세팅하는게 좀더 자연스럽다(?)고 생각해서 그렇게 했다.

import java.util.*;
import java.io.*;

public class Main {
    public static int solution(String a, String b) {
        int answer = 0;
        Map<Character, Integer> aMap = new HashMap<>();
        Map<Character, Integer> bMap = new HashMap<>();

        for (char x : b.toCharArray()) {
            bMap.put(x, bMap.getOrDefault(x, 0) + 1);
        }
        int lengthB = b.length();

        for (int i = 0; i < lengthB; i++) {
            aMap.put(a.charAt(i), aMap.getOrDefault(a.charAt(i), 0) + 1);
        }

        if (aMap.equals(bMap)) answer++;

        int lengthA = a.length();
        int left = 0;
        for (int right = lengthB; right < lengthA; right++) {
            aMap.put(a.charAt(right), aMap.getOrDefault(a.charAt(right), 0) + 1);

            if (aMap.get(a.charAt(left)) > 1) {
                aMap.put(a.charAt(left), aMap.get(a.charAt(left)) - 1);
            } else {
                aMap.remove(a.charAt(left));
            }

            left++;
            if (aMap.equals(bMap)) answer++;
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String S = br.readLine();
        String T = br.readLine();

        System.out.println(solution(S, T));
    }
}

 

 

강사님의 풀이

import java.util.*;

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 x : b.toCharArray()) bm.put(x, bm.getOrDefault(x, 0) + 1);
		
        int L = b.length() - 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.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 T = new Main();
		Scanner kb = new Scanner(System.in);
		String a = kb.next();
		String b = kb.next();
		System.out.print(T.solution(a, b));
	}
}

 

 

 

구독과 공감♡♡은 블로그 운영에 큰 힘이 됩니다!
긍정적인 댓글 남겨주시면 감사드리며,
보완해야 할 점이 있으면 댓글로 남겨주셔도 좋습니다!