[SWEA] 3816. 아나그램

[SWEA] 3816. 아나그램

제출일 : 2019-12-11

문제 풀이 시간 : 1H 45M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4#

아나그램이란 문자열의 문자들을 모두 사용하여 재배열한 것을 의미한다.

“abc”의 아나그램은 “abc”, “acb”, “bac”, “bca”, “cab”, “cba” 총 6개이다.

문자열 S1, S2이 차례대로 주어진다. S2의 부분문자열 중 S1의 아나그램인 것의 개수를 구하는 프로그램을 작성하라.

input

첫 줄에 테스트케이스의 개수 T가 주어진다. (T ≤ 20)

각 테스트케이스의 첫 줄에 S1, S2가 사이에 공백을 갖고 띄어져 있다.

S1과 S2는 영문 소문자로만 이루어져 있다. (1 ≤ |S1| ≤ |S2| ≤ 100,000)(|S1|, |S2|는 문자열 S1, S2의 길이)

Output

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 해당 테스트케이스의 아나그램인 것의 개수를 출력한다.

Example

input

4
aba ababababa
abra abracadabra
anan bananaparanabrazil
ab abba

output

#1 4
#2 2
#3 2
#4 2

Solution & Inpression

아나그램이란 문자열의 문자들을 모두 사용하여 재배열한 것이므로 아나그램이 가능한 경우는 사용되는 알파벳의 조합과 그 숫자가 정확하게 일치될때 아나그램이라고 말한다.

따라서 S2의 부분 문자열이 S1의 아나그램이 되려면 S1이 가진 알파벳의 조합과 사용된 수를 구해 counts 배열에 저장하고 각각 탐색하면서 문제를 해결한 풀이가 code1의 풀이이다.

code1의 풀이는 어렵지 않게 구현이 가능했다.

code2는 S2의 부분 문자열을 탐색할때 순차적으로 탐색을 하기에 맨앞의 알파벳과 맨 뒤의 알파벳만이 변경되며 나머지 알파벳은 그대로 사용되기에 양 끝의 알파벳만 확인하며 아나그램을 찾았다.

Code 1

언어 : JAVA

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input.txt"));

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            char[] s1 = sc.next().toCharArray();
            char[] s2 = sc.next().toCharArray();
            int[] counts = new int[26];

            for (int i = 0; i < s1.length; i++) {
                counts[s1[i] - 'a']++;
            }

            int ans = 0;

            for (int i = 0; i < s2.length - s1.length + 1; i++) {
                int[] tmp = new int[26];
                for (int j = i; j < s1.length + i; j++) {
                    tmp[s2[j] - 'a']++;
                }
                boolean flag = true;
                for (int k = 0; k < 26; k++) {
                    if (tmp[k] != counts[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans++;
            }

            System.out.println("#" + tc + " " + ans);

        } // end of TC

    }// end of main
}

Code 2

언어 : JAVA

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            String str1 = sc.next();
            String str2 = sc.next();

            int ans = 0;
            int[] counts = new int[26];

            for (int i = 0; i < str1.length(); i++) {
                counts[str1.charAt(i) - 'a']++;
            }

            int zero = 0;
            for (int i = 0; i < 26; i++) {
                if (counts[i] == 0) {
                    zero++;
                }
            }

            int len = str1.length();
            for (int i = 0; i < str2.length(); i++) {
                char a = str2.charAt(i);

                if (counts[a - 'a'] == 0) {
                    zero--;
                }
                counts[a - 'a']--;
                if (counts[a - 'a'] == 0) {
                    zero++;
                }


                if (i >= len) {
                    char b = str2.charAt(i - len);
                    if (counts[b - 'a'] == 0) {
                        zero--;
                    }
                    counts[b - 'a']++;
                    if (counts[b - 'a'] == 0) {
                        zero++;
                    }
                }


                if (zero == 26) {
                    ans++;
                }
            }
            System.out.println("#" + tc + " " + ans);
        }
    }
}