모든 아나그램 찾기(Hash, sliding window : 시간복잡도 O(n))

설명

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

입력

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

출력

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

public class Main {
    public int solution(String s, String t) {
    
        int answer = 0, lt = 0;
        // 아나그램의 기준이 되는 문자열의 해시맵 tmap
        HashMap<Character, Integer> tmap = new HashMap<>();
        // 비교당할 문자열의 해시맵 smap
        HashMap<Character, Integer> smap = new HashMap<>();

        for (char tt : t.toCharArray()) tmap.put(tt, tmap.getOrDefault(tt, 0) + 1);
        
        // 🌸 꽃을 단 for문이 시작할 때 바로 put 할 것이기 때문에 smap은 size t.length()-1 로 설정
        int x = t.length() - 1;
        
        for (int i = 0; i < x; i++) smap.put(s.charAt(i), smap.getOrDefault(s.charAt(i), 0) + 1);

        // 🌸
        for (int rt = x; rt < s.length(); rt++) {
            // smap에 key value 추가
            smap.put(s.charAt(rt), smap.getOrDefault(s.charAt(rt), 0) + 1);
            
            // smap과 tmap 비교
            if (tmap.equals(smap)) {
                answer++;
                // s문자열의 lt 배열의 값 -1
                smap.put(s.charAt(lt), smap.get(s.charAt(lt)) - 1);
                // s문자열의 lt 인덱스의 값이 0이면 key 삭제
                if (smap.get(s.charAt(lt)) == 0) smap.remove(s.charAt(lt));
                lt++;
            } else {
                smap.put(s.charAt(lt), smap.get(s.charAt(lt)) - 1);
                if (smap.get(s.charAt(lt)) == 0) smap.remove(s.charAt(lt));
                lt++;
            }
        }

        return answer;
    }
}

HashMap에 equals() 메서드가 있는줄 모르고 아주 먼길을 돌아왔다.
맨 처음 풀이방법은 지금 생각해보면 이상했다.

t문자열에 대한 해시맵(map)을 만들고 해시맵을 복사해둔 후에(copymap) copymap과 s문자열 자체를 비교해가며 rt 인덱스에 해당하는 s문자를 copymap에서 빼거나 삭제했다.
그리고 copymap의 size가 0이면 answer를 더하고 다시 copymap을 생성하는...

답이 안나오고 계속 수정을 하다보니 나중에는 내가 봐도 헷갈릴만큼 더러운 코드가 돼버렸다.

오기로 풀지않고 아니다 싶을때 다른 방법을 고려해보는 용기를 좀 가지고 내일은 오늘보다 더 좋은 방법을 떠올렸으면 좋겠다.

아직 알고리즘 초급단계라 막막 그 자체이지만,, 내일은 오늘보다 더 낫겠지!🌸