[문제풀이] 04-04. 모든 아나그램 찾기

인프런, 자바(Java) 알고리즘 문제풀이

HashMap, TreeSet(자료구조) - 0404. 모든 아나그램 찾기

🗒️ 문제

🎈 나의 풀이

	private static int solution(char[] str1, char[] str2) {
        int answer = 0;
        boolean anagram;
        HashMap<Character, Integer> map = new HashMap<>();

        for(char s : str2) map.merge(s, 1, Integer :: sum);

        for(int i=0; i<str1.length - str2.length + 1; i++) {
            HashMap<Character, Integer> compare = new HashMap<>(map);
            anagram = true;

            for(int j=0; j<str2.length; j++) {
                if (!compare.containsKey(str1[i + j]) || compare.get(str1[i + j]) <= 0) {
                    anagram = false;
                    break;
                }
                compare.merge(str1[i + j], -1, Integer :: sum);
            }

            if(anagram) answer++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] arr1 = sc.nextLine().toCharArray();
        char[] arr2 = sc.nextLine().toCharArray();
        System.out.println(solution(arr1, arr2));
    }

🖍️ 강의 풀이

    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));
	}

💬 짚어가기

해당 문제는 앞선 아나그램 문제와 매출액의 종류 문제를 합쳤다고 볼 수 있다.
비교 대상이 되는 문자열을 Map에 보관하고, 전체 문자열을 sliding window로 순회하며
아나그램 여부를 판별하는 로직이다.

나의 풀이의 경우 기준이 되는 Map을 매 반복마다 복사하여 사용하도록 하였고, 강의에서는 현재
순회하는 문자열을 담을 Map을 하나 더 생성하고, 두 자료를 equals() 메소드로 비교하였다.
메모리 사용 측면에서 강의 방식이 더 좋은 것 같다.