equals() 사용 시 시간 복잡도 관련 질문

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

    }
}

import java.util.*;
class Main {	
	public int solution(String a, String b){
		int answer = 0;
		HashMap<Character, Integer> sH = new HashMap<>();
		for(char x : b.toCharArray()) sH.put(x, sH.getOrDefault(x, 0) - 1);
		int L = b.length()-1;
		for(int i = 0; i < L; i++){
			sH.put(a.charAt(i), sH.getOrDefault(a.charAt(i), 0) + 1);
			if(sH.get(a.charAt(i)) == 0) sH.remove(a.charAt(i));
		}
		int lt = 0;
		for(int rt = L; rt < a.length(); rt++){
			sH.put(a.charAt(rt), sH.getOrDefault(a.charAt(rt), 0) + 1);
			if(sH.get(a.charAt(rt)) == 0) sH.remove(a.charAt(rt));
			if(sH.size() == 0) answer++;
			sH.put(a.charAt(lt), sH.getOrDefault(a.charAt(lt), 0) - 1);
			if(sH.get(a.charAt(lt)) == 0) sH.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));
	}
}