상습적으로 틀리는 알고리즘 Hashmap

내가 자주 틀리는 알고리즘 유형 정리 🤷‍♂️

---

Hash, sliding window : 시간복잡도 O(n)

key point는 pointer 개념을 이용해서 풀어야한다.

1. 초기값 세팅시 -1 만큼 map에 저장
2. 방향 lp, rp 개념을 이용하기
3. String에 저장하기보단 동적 메모리 arraylist를 쓰자.

   Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> compare = new HashMap<>();
   
        int counter = 0;
        //초기값 세팅
        for (int i = 0 ; i < word.length() ; i++){
            map.put(word.charAt(i), map.getOrDefault(word.charAt(i),0)+1);
            compare.put(str.charAt(i), compare.getOrDefault(str.charAt(i), 0) + 1);
        }
        compare.put(str.charAt(word.length() - 1), compare.getOrDefault(str.charAt(word.length() - 1),0)-1);
        int lp = 0; // 왼쪽 좌표
   
        for (int rp = word.length() - 1; rp < str.length(); rp++) {
            char Rchar = str.charAt(rp);
            char Lchar = str.charAt(lp);
   
            compare.put(Rchar, compare.getOrDefault(Rchar,0)+1); //rp 한칸 전진
            if(map.equals(compare)) counter++;
   
            compare.put(Lchar, compare.getOrDefault(Lchar,0)- 1); //왼쪽 값 삭제
            if(compare.get(Lchar)==0) compare.remove(Lchar);
   
            lp++;
        }
        System.out.println(counter);
   

재귀함수 메모이제이션

import java.io.*;
import java.util.*;

public class Main {
    static int[] fibo;
    private static int solution(int i) {
        if(fibo[i]>0) return fibo[i]; // 메모이제이션 포인트 
        //어차피 배열은 0으로 세팅되어있는데 값이 바뀌면 계산해놓은걸 참고해서 쓰면 좋지않은가

        if (i == 1) return fibo[i] = 1;
        else if (i == 2) return fibo[i] = 1;
        else return fibo[i] = solution(i - 2) + solution(i - 1);

    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int i = Integer.parseInt(br.readLine());
        fibo = new int[i + 1];
        solution(i);
        for (int x = 1 ; x < fibo.length ; x++)
            System.out.printf(fibo[x]+" ");
    }
}