[알고리즘] 모든 아나그램 찾기 with Java

O(N)으로 풀려했지만 도저히 풀 수 없어서 O(N^2)로 풀어본 문제. 정답은 맞았는데 과연,, 해설도 동일할까? 궁금

 

오늘 배운 것

1. equals

. hashmap도 equals가 적용된다.

2. 문제 풀이

. 하나씩 올라가고, 하나씩 빼주는 방식으로 진행된다.

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

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        String s1 = kb.next();
        String s2 = kb.next();
        solution(s1, s2);
    }

    private static void solution(String s1, String s2) {
        int answer = 0, lt = 0;
        HashMap<Character, Integer> s2_hashmap = new HashMap<>();
        HashMap<Character, Integer> s1_hashmap = new HashMap<>();
        for (char c : s2.toCharArray()) {
            s2_hashmap.put(c, s2_hashmap.getOrDefault(c, 0) + 1);
        }
        char[] s1_arr = s1.toCharArray();
        for (int i = 0; i < s2.length() - 1; i++) {
            s1_hashmap.put(s1_arr[i], s1_hashmap.getOrDefault(s1_arr[i], 0) + 1);
        }
        for (int rt = s2.length() - 1; rt < s1.length(); rt++) {
            s1_hashmap.put(s1_arr[rt], s1_hashmap.getOrDefault(s1_arr[rt], 0) + 1);
            if (isAna(s2_hashmap, s1_hashmap)) {
                answer++;
            }
            s1_hashmap.put(s1_arr[lt], s1_hashmap.get(s1_arr[lt]) - 1);
            if (s1_hashmap.get(s1_arr[lt]) == 0) s1_hashmap.remove(s1_arr[lt]);
            lt++;
        }
        System.out.println(answer);
    }

    private static boolean isAna(HashMap<Character, Integer> s2_hashmap, HashMap<Character, Integer> s1_hashmap) {
        for (char c : s2_hashmap.keySet()) {
            if (s1_hashmap.getOrDefault(c, 0) == 0) {
                return false;
            }
            if (s1_hashmap.get(c) != s2_hashmap.get(c)) {
                return false;
            }
        }
        return true;
    }
}

. 강의에서는 이중for문을 도는것이 아닌 equals메서드로 끝냈다. 새로운 것을 배웠다.

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

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        String s1 = kb.next();
        String s2 = kb.next();
        solution(s1, s2);
    }

    private static void solution(String s1, String s2) {
        int answer = 0, lt = 0;
        HashMap<Character, Integer> s2_hashmap = new HashMap<>();
        HashMap<Character, Integer> s1_hashmap = new HashMap<>();
        for (char c : s2.toCharArray()) {
            s2_hashmap.put(c, s2_hashmap.getOrDefault(c, 0) + 1);
        }
        char[] s1_arr = s1.toCharArray();
        for (int i = 0; i < s2.length() - 1; i++) {
            s1_hashmap.put(s1.charAt(i), s1_hashmap.getOrDefault(s1.charAt(i), 0) + 1);
        }
        for (int rt = s2.length() - 1; rt < s1.length(); rt++) {
            s1_hashmap.put(s1.charAt(rt), s1_hashmap.getOrDefault(s1.charAt(rt), 0) + 1);
            /*if (isAna(s2_hashmap, s1_hashmap)) {
                answer++;
            }*/
            // 이부분을 equals메서드로 개선함
            if (s1_hashmap.equals(s2_hashmap)) {
                answer++;
            }
            s1_hashmap.put(s1_arr[lt], s1_hashmap.get(s1_arr[lt]) - 1);
            if (s1_hashmap.get(s1_arr[lt]) == 0) s1_hashmap.remove(s1_arr[lt]);
            lt++;
        }
        System.out.println(answer);
    }

    /*private static boolean isAna(HashMap<Character, Integer> s2_hashmap, HashMap<Character, Integer> s1_hashmap) {
        for (char c : s2_hashmap.keySet()) {
            if (s1_hashmap.getOrDefault(c, 0) == 0) {
                return false;
            }
            if (s1_hashmap.get(c) != s2_hashmap.get(c)) {
                return false;
            }
        }
        return true;
    }*/
}