인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요 강사님 좋은 강의 항상 감사드립니다.

해당 문제에서 시간 복잡도 관련 질문이 있습니다!

map의 equals() 는 내부적으로 O(n)의 복잡도를 가진 메소드로 알고 있습니다! 내부 구현 코드도 entrySet을 통해서 반복문으로 찾는 과정이 있는 것 같은데요!

그렇다면 for문 안에 equals()를 사용할 경우 O(n^2)이 되는 것이 아닌지 질문 드리고 싶습니다! equals가 평균적으로 n 까지 가지 않기 때문에 제외 되는 것일까요?

추가적으로 equals() 를 사용하지 않고 풀이를 해봤습니다! 채점을 했을 땐 통과를 하였는데.. 혹시 이 방법에 예외가 있을까요?

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

public class Main {
    private static void solution(String s, String t) {
        int idx1 = 0;
        int answer = 0;
        int cnt = 0;
        HashMap<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < s.length(); i++) {
            char key = s.charAt(i);
            if (targetMap.containsKey(key)) {
                int value = targetMap.get(key);
                if (value == 0) {
                    cnt--;
                }
                targetMap.put(key, --value);
                if (value == 0) {
                    cnt++;
                }
            }
            if (i >= t.length()) {
                char backKey = s.charAt(idx1++);
                if (targetMap.containsKey(backKey)) {
                    int value = targetMap.get(backKey);
                    if (value == 0) {
                        cnt--;
                    }
                    targetMap.put(backKey, ++value);
                    if (value == 0) {
                        cnt++;
                    }

                }
            }
            if (cnt == targetMap.size()) {
                answer++;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        solution(s, t);

    }
}