[Inflearn] 자바 알고리즘 문제풀이 #04-04 4. 모든 아나그램 찾기(Hash, sliding window)

문제

설명

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

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

 

입력 

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

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

 

출력 

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

 

 

 

내 풀이

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

public class Main4_4 {
    public int Solution(String s, String t) {
        int answer=0, cnt;
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i = 0; i <= s.length()-t.length(); i++) {
            for (int j = i; j < i+t.length(); j++) {
                hm.put(s.charAt(j), hm.getOrDefault(s.charAt(j), 0)+1);
            }
            for(char x : t.toCharArray()) {
                hm.put(x, hm.getOrDefault(x, 0)-1);
            }
            cnt=0;
            for (char key : hm.keySet()) {
                if(hm.get(key)==0) cnt++;
            }
            if(cnt==t.length()) answer++;
            hm.clear();
        }
        return answer;
    }

    public static void main(String[] args) {
        Main4_4 T = new Main4_4();
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        System.out.println(T.Solution(s, t));
    }
}

HashMap 비교는 그냥 단순하게 객체니까 equals()로 비교해도 되는지 몰랐다. ("키-값"을 일일이 비교해야 하는 줄..)

그래서 같은 hm으로 문자열1은 더해주고 문자열2는 빼주는 방식으로는 위의 코드처럼 구현할 수 밖에 없었다.

잘 풀었다고 생각했지만 5개의 테스트 케이스 중 1개가 통과되지 못해 오답처리 되었다. 이중 for문이라 걱정했던 시간초과도 아니고....

왜 틀렸는지는 아직도 잘 모르겠다..... 나의 최선이었단 말이야......

 

 

 

선생님 풀이

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

public class Main4_4 {
    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) {
        Main4_4 T = new Main4_4();
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        System.out.println(T.Solution(a, b));
    }
}

이제 슬라이딩 윈도우, HashMap 모두 익숙해졌다. equals로 비교해도 된다는 설명만 듣고 정답 코드를 구현했으니 ㅎㅎ 뿌듯뿌듯

오늘도 하나 알아가니, 기분이 좋다.

 

 

 

결과