알고리즘) 모든 아나그램 찾기

 문자열 S와 T가 주어지고, S에서 문자열 T와 아나그램이 되는 부분문자열의 개수를 출력하는 문제이다. 첫 줄에 S가, 다음 줄에 T가 입력된다. 주어지는 문자열의 각 문자를 해싱해서 문자의 개수를 value로 삼는 것이 기본이 된다. 여기에 문자 T는 항상 S보다 짧은 문자열이고, S 내에서 T와 아나그램인 연속되는 문자를 찾는 것이기 때문에, T의 길이만큼 sliding-window 알고리즘 기법을 사용하면 된다. 사실 처음에 two-pointer 알고리즘 기법도 함께 적용하려 했으나 다른 문제로 실패하면서 보류하게 되었다. 이후에 코드를 개선할 때 추가할 예정이다.

 

많은 시간이 소요된 부분

  two-pointer, sliding-window 알고리즘을 사용하기 위해 문자열 T를 해싱할 때 S 문자열의 처음부터 T 길이만큼의 문자열을 함께 해싱하고, while문이 rt(window 마지막 인덱스)가 S의 길이보다 작으면 계속해서 돌게 하는 것이 목표였다. 그러다보니 첫 루프가 무조건 문자열 S의 인덱스 '0 ~ T.length() - 1'의 해시 테이블과 T 해시 테이블을 비교해야만 했는데, 이 루프 마지막에 다음 window의 해시 테이블을 완성하려 했더니 문제가 발생했다. 루프가 실행되는 조건(실행되어야만 일치 여부 검증이 가능하다.)은 rt가 S의 길이보다 작은 값이어야 한다는 것인데, 이 때 rt가 S의 마지막 인덱스일 경우에는 루프 마지막에 다음 window의 해시 테이블을 만드는 과정에서 Index Out of Bound Exception이 발생하는 것이었다..

 그래서 첫 해시 테이블을 만들 때 T 길이보다 1 작게 만들어서 루프가 시작될 때 현재 rt( = T의 마지막 인덱스와 같은 값)의 문자를 해싱한 데이터를 해시 테이블에 추가하고 검증한다. 검증이 이루어진 이후에 lt(윈도우의 시작 인덱스)를 1 증가시키는 작업을 한다. 이렇게 되면 rt는 S의 마지막 인덱스까지 도달해서도 그 상태의 해시 테이블을 생성하여 아나그램임을 검증할 수 있다.

 인덱스를 고려하는 작업이 생각보다 어렵다.. 알고리즘 마스터가 되는 그 날까지..🐣

 

작성 코드

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

public class Main {
    private int solution(String s, String t) {
        int answer = 0, idx = 0, len = t.length();

        Map<Character, Integer> tMap = new HashMap<>();
        Map<Character, Integer> sTempMap = new HashMap<>();

        for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        for (int i = 0; i < t.length() - 1; i++)
            sTempMap.put(s.charAt(idx), sTempMap.getOrDefault(s.charAt(idx++), 0) + 1);

        for (int i = idx; i < s.length(); i++) {
            sTempMap.put(s.charAt(i), sTempMap.getOrDefault(s.charAt(i), 0) + 1);

            boolean flag = true;
            if (tMap.size() == sTempMap.size()) {
                for (char c : tMap.keySet()) {
                    if (sTempMap.get(c) != tMap.get(c)) {
                        flag = false;
                        break;
                    }
                }

                if (flag) {
                    answer++;
                }
            }
            
            sTempMap.put(s.charAt(i - len + 1), sTempMap.get(s.charAt(i - len + 1)) - 1);
            if (sTempMap.get(s.charAt(i - len + 1)) == 0) sTempMap.remove(s.charAt(i - len + 1));
        }
        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();
        String t = sc.nextLine();
        System.out.println(al.solution(s, t));
    }
}

 

개선 코드

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

public class Main {
    private int solution(String s, String t) {
        int answer = 0, idx = 0, lt = 0, len = t.length();

        Map<Character, Integer> tMap = new HashMap<>();
        Map<Character, Integer> sTempMap = new HashMap<>();

        for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        for (int i = 0; i < len - 1; i++)
            sTempMap.put(s.charAt(idx), sTempMap.getOrDefault(s.charAt(idx++), 0) + 1);

        for (int rt = idx; rt < s.length(); rt++) {
            sTempMap.put(s.charAt(rt), sTempMap.getOrDefault(s.charAt(rt), 0) + 1);

            if (tMap.equals(sTempMap)) answer++;

            sTempMap.put(s.charAt(lt), sTempMap.get(s.charAt(lt)) - 1);
            if (sTempMap.get(s.charAt(lt)) == 0) sTempMap.remove(s.charAt(lt));
            lt++;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();
        String t = sc.nextLine();
        System.out.println(al.solution(s, t));
    }
}

 

 two-pointer 알고리즘을 사용하기 위해 인덱스로 사용하는 변수가 늘어났으나 코드의 흐름은 그대로이다.

 이 문제의 포인트는 S의 첫 해시 테이블을 생성할 때 T의 길이보다 1 작게 만들고, 루프를 시작하는 인덱스를 T의 길이로 두게끔 한다는 점이다. 또한, Java의 Map이 제공하는 equals() 메서드는 서로 다른 객체인 맵 인스턴스끼리도 그 내용(key와 value의 조합)이 같으면 참(true)을 반환한다는 점이다. 실제로 T의 keySet()을 통해 key를 돌려 비교하는 코드가 equals() 메서드로 인해 한 줄로 줄어들었다.