[SWEA] 3816 아나그램

출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms

 Input 

4

aba ababababa

abra abracadabra

anan bananaparanabrazil

ab abba

 

 Output 

#1 4

#2 2

#3 2

#4 2

 

① S1을 문자를 int형 배열에 저장한다. (Alphabet 빈도 수를 저장)

② S2를 S1의 길이만큼 부분문자열 구해서 int형 배열로 변환한다.

③ 알파벳 개수를 통해 Anagram 여부를 판단.　

---

import java.util.Scanner;
 
public class Solution {     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // TestCase 개수
        int T = Integer.parseInt(sc.next());
         
        for(int tc=1; tc<=T; tc++) {
            // input
            char[] A = sc.next().toCharArray();
            char[] B = sc.next().toCharArray();
             
            // A 문자열을 알파뱃 개수 배열로 변환
            int [] aArr = makeAlphabet(A, 0, A.length);
             
            int lengthOfA = A.length;
            int i = 0;
            int ans = 0;
             
            while(true) {
                if(i+lengthOfA > B.length) break;
                // A의 길이 만큼 B의 부분문자열을 가져온다.
                int[] bArr = makeAlphabet(B, i, i+lengthOfA);
                // 부분문자열이 아나그램인지 확인
                if(isAnagram(aArr, bArr)) ans++;
                i++;
            }
            System.out.print("#" + tc + " ");
            System.out.println(ans);
        }
    }
     
    public static int[] makeAlphabet (char[] arr, int start, int end){
        int[] alphabet = new int[26];
        for (int i = start; i < end; i++) {
            alphabet[arr[i] - 'a']++; 
        }
        return alphabet;
    }
     
    private static boolean isAnagram(int[] aArr, int[] bArr) {
        for(int i=0; i<aArr.length; i++) {
            if(aArr[i] != bArr[i]) return false;
        }
        return true;
    }
}