[해쉬, 투포인터, 슬라이딩] 4. 모든 아나그램 찾기

4. 모든 아나그램 찾기

 

설명

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.

아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

입력

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.

S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

출력

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

예시 입력 1 

bacaAacba
abc

예시 출력 1

3

힌트

출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

 

 

<<풀이>>

 

-나의 풀이- 

 

시간 복잡도 : O(N)

풀이 1

 

일단 내 풀이가 두 개인데 ㅋㅋ 하나는 어디선가 틀렸다 ... 그래서 좀 도움을 받아 두 번째 풀이를 받을 수 있었다.

 

나도 나름 투포인터와 해쉬를 이용해서 구했다.

 

원리는 우선 a, b, c 를 map에 넣어두고 비교하면서 같은게 있다면 -1 하는 방식으로 했고, 최종적으로 value가 전부다 0이되면 count++되는 식으로 했다.

 

근데, 계속 틀려서 원인을 파악했더니 

import java.util.*;

class Main {

    public int solution(String str, String target) {
        HashMap<Character, Integer> map = new HashMap<>();
        int lt = 0, count = 0;
        for(char x : target.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        char[] arr = str.toCharArray();


        for(int rt = lt + 1; rt < lt + str.length(); rt++) {
            map.put(arr[rt], map.getOrDefault(map.get(arr[rt]), 0) - 1);
            if(map.size() > target.length() || map.get(arr[rt]) < 0) {
                lt++;
                rt = lt + 1;
                map.clear();
                continue;
            }
            if(rt == lt + str.length() - 1) {
                count++;
                lt++;
                rt = lt + 1;
                map.clear();
            }
        }

        return count;
    }


    public static void main(String[] args ){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String str = in.next();
        String target = in.next();

        System.out.println(T.solution(str, target));
    }
}

 

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 9 out of bounds for length 9
at Main.solution(Main.java:16)
at Main.main(Main.java:41)

이런 오류가 뜬다 ㅠ 마음 같아서 하나하나 찾아서 원인을 분석하고 싶지만, 다른 것도 해야하기 때문에 다음을 기약하며 일단 넘어간다 !!

 

풀이 2

 

시간 복잡도 = O(N)

 

우선 정답!

 

이렇게 나왔다. 아직 정확하게 원인이 무엇인지는 알 수 있지만, 풀이2의 코드는 직관적으로 보인다.

 

내가 하고 싶어하던 방식과 크게 다르지 않지만 조금 다르다.

 

메서드를 두 번 사용했다. 하나의 메서드가 또 다른 메서드를 사용해서 값을 도출 한 후, 최종 실행 클래스에 반환한다.

 

이렇게 코드가 길어지거나 하면 메서드를 하나 더 만들어서 진행하면 좋다 !!!

 

import java.util.*;

class Main {

    public int solution(String str, String target) {
        HashMap<Character, Integer> map = new HashMap<>();
        int lt = 0, count = 0, targetLen = target.length();

        // target의 각 문자를 맵에 추가
        for(char x : target.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        char[] arr = str.toCharArray();
        int windowSize = 0;

        // 주어진 문자열을 순회
        for(int rt = 0; rt < arr.length; rt++) {
            char ch = arr[rt];
            // 현재 문자가 target에 있는 경우, 맵에서 하나 줄임
            map.put(ch, map.getOrDefault(ch, 0) - 1);
            windowSize++;

            // 윈도우 크기가 target의 길이와 같아지면
            if(windowSize == targetLen) {
                // 윈도우 내 모든 문자가 target에 있는지 확인
                if(isAllZero(map)) {
                    count++;
                }
                // lt 위치의 문자를 다시 추가
                map.put(arr[lt], map.getOrDefault(arr[lt], 0) + 1);
                lt++;
                windowSize--;
            }
        }

        return count;
    }

    // 맵의 모든 값이 0인지 확인하는 함수
    private boolean isAllZero(HashMap<Character, Integer> map) {
        for(int value : map.values()) {
            if(value != 0) return false;
        }
        return true;
    }

    public static void main(String[] args ){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String str = in.next();
        String target = in.next();

        System.out.println(T.solution(str, target));
    }
}

 

 if(windowSize == targetLen) {
                // 윈도우 내 모든 문자가 target에 있는지 확인

                if(isAllZero(map)) {
                    count++;
                }
                // lt 위치의 문자를 다시 추가
                map.put(arr[lt], map.getOrDefault(arr[lt], 0) + 1);
                lt++;
                windowSize--;
            }
        }

 

이 부분이 이해가 안 되었는데, 잘 살펴보면 우리는 map을 미리 지정해두고 for문을 돌면서 그 값이 있으면 -1하고 있다. 이때, 끝나고 윈도우가 이동을하면서 좌측 값은 사용하지 않기 때문에 일단 추가시켜주고 lt++를 하는 것이다.

 

아마 글로는 이해하기 힘들 수 있다. 문제를 잘 읽고 논리적으로 접근하면 그 활용을 알 수 있다.

 

-강사님 풀이-

 

import java.util.*;

class Main {

    public int solution(String str, String target) {
      int answer = 0;
      HashMap<Character, Integer> am = new HashMap<>();
      HashMap<Character, Integer> bm = new HashMap<>();
      for (char x : target.toCharArray()) am.put(x, am.getOrDefault(x, 0) + 1);
      int L = target.length() - 1;
      for (int i = 0; i < L; i++) bm.put(str.charAt(i), bm.getOrDefault(str.charAt(i), 0) + 1);
      int lt = 0;
        for (int rt = L; rt < str.length(); rt++) {
            bm.put(str.charAt(rt), bm.getOrDefault(str.charAt(rt), 0) + 1);
            if (bm.equals(am)) answer++;
            bm.put(str.charAt(lt), bm.get(str.charAt(lt)) - 1);
            if (bm.get(str.charAt(lt)) == 0) bm.remove(str.charAt(lt));
            lt++;
        }
        return answer;
    }


    public static void main(String[] args ){
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String str = in.next();
        String target = in.next();

        System.out.println(T.solution(str, target));
    }
}

 

후후 역시 깔끔하게 푸셨다!

 

여기서 특이점은 equals라는 메서드인데 ~ 나도 처음에는 이걸 생각은 했다. 하지만 해쉬맵을 사용할 때 넣는 순서가 다르면 위치가 달라져서 equals가 안 될 줄 알았다. 하지만 넣는 순서 상관없이 움직인다는 점!!

 

또한, 슬라이딩할때 미리 비교 대상 전까지 셋팅하고 시작하게 되면 굳이 사이즈를 설정해놓고 시작해서 사이즈가 같아지면 ~~ 이라는 구조가 없어진다. 그냥 하나 증가하고 비교하고 그 다음 진행하고 이런식이다.

 

왜 초기 셋팅을 하는지 알 수 있었다.

 

처음에 투포인터와 어떤 점이 그렇게 다른가 생각했는데 이것이 슬라이딩 윈도우를 제대로 활용한 점인가 싶다!!

 

오늘도 배워갑니당