자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Hash, sliding window : 시간복잡도 O(n)_모든 아나그램 찾기)

 

 

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

 

예시 입력 1 

10 3
13 15 34 23 45 65 33 11 26 42

예시 출력 1

143

 

 

내가 푼 첫번째 틀린 풀이

맨 처음에는 map에서 equals함수가 된다는걸 모르고 엄청난 뻘짓을 했다,,

map.get(key)로 나온 value값이 서로 일치하는지로 해봤더니, 이전에 A부분에서 지나간건 체크를 못하더라.

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

public class Main {

    public int solution(String str, String t) {

        int answer = 0;

        HashMap<Character, Integer> target = new HashMap<>();
        for (Character x : t.toCharArray()) {
            target.put(x, target.getOrDefault(x, 0) + 1);
        }

        HashMap<Character, Integer> HM = new HashMap<>();
        int lt = 0;
        for (int rt = 0; rt < str.length(); rt++) {
            char key = str.charAt(rt);
            HM.put(key, HM.getOrDefault(key, 0) + 1);
            System.out.println(HM);
            if (HM.get(key) == target.get(key)) {
                System.out.println("---A를 찾아라---");
                System.out.println(key);
                System.out.println("HM.get(key) : " + HM.get(key));
                System.out.println("target.get(key) : " + target.get(key));
                System.out.println("key의 벨류가 같은지 검증 확인");
                if (target.size() == HM.size()) {
                    System.out.println("answer추가됨");
                    answer++; // 미완성,,,
                }
            }
            if (rt - lt + 1 == t.length()) {
                HM.put(str.charAt(lt), HM.get(str.charAt(lt)) - 1);
                if (HM.get(str.charAt(lt)) == 0) HM.remove(str.charAt(lt)); // 키 삭제
                lt++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        String t = kb.next();
        System.out.println(T.solution(str, t));
    }
}

 

내가 푼 두번째 풀이(Time: 179ms Memory: 28MB)

Map의 equals()를 사용했다.

나는 따로 str에 대한 map을 초반에 세팅해주진 않았는데, 강의에서는 세팅해줬다.

미리 세팅해놓고, 그 다음 조건부터 put을 하는게 더 좋은 것 같다.그리고 나는 설정 구간과 t의 길이가 일치하는 경우를 조건문으로 붙였는데, 강의처럼 그냥 바로 equals하면 편한것같다.

어차피 맵의 equals는 키와 벨류까지 다 일치하는지 확인해주기 때문이다.

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

public class Main {

    public int solution(String str, String t) {

        int answer = 0;

        HashMap<Character, Integer> target = new HashMap<>();
        for (Character x : t.toCharArray()) {
            target.put(x, target.getOrDefault(x, 0) + 1);
        }

        HashMap<Character, Integer> HM = new HashMap<>();
        int lt = 0;
        for (int rt = 0; rt < str.length(); rt++) {
            char key = str.charAt(rt);
            HM.put(key, HM.getOrDefault(key, 0) + 1);
            // 설정한 구간과 t의 길이가 일치하는 경우
            if (rt - lt + 1 == t.length()) {
                if (HM.equals(target)) { // HM과 target을 비교하여 모든 문자의 개수가 일치하는지 확인
                    answer++;
                }
                HM.put(str.charAt(lt), HM.get(str.charAt(lt)) - 1);
                if (HM.get(str.charAt(lt)) == 0) HM.remove(str.charAt(lt)); // 키 삭제
                lt++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        String t = kb.next();
        System.out.println(T.solution(str, t));
    }
}

 

 

강의 풀이 (Time: 172ms Memory: 28MB)

b의 길이 하나 전까지 am을 다 세팅해준 다음에 rt를 움직이면서 업데이트 한다.

자바에는 두 객체(맵)을 비교하는 equals()라는 함수가 있는데, 키값 카운팅한 벨류값까지 다 봐준다.

HM : {a=1, b=1, c=1}
target : {a=1, b=1, c=1}

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

public class Main {
    public int solution(String a, String b) {
        int answer = 0;
        HashMap<Character, Integer> am = new HashMap<>();

        // 먼저 bm 세팅하기
        HashMap<Character, Integer> bm = new HashMap<>();
        for (char x : b.toCharArray()) bm.put(x, bm.getOrDefault(x, 0) + 1);

        // am 세팅해놓기, b의 길이보다 하나 적게 세팅
        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;
        // 투포인터랑 슬라이딩 윈도우로 rt부터 쭈욱 am 업데이트하기
        for (int rt = L; rt < a.length(); rt++) {
            am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0) + 1);
            // 해쉬맵의 equals를 할 줄 아는게 매우 중요!!!!
            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) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        String a = kb.next();
        String b = kb.next();
        System.out.println(T.solution(a, b));
    }
}