모든 아나그램 찾기

 

문제 이해

 

아나그램은 순서 상관없이 구성이 같으면 아나그램이라고 한다. 이 문제는 모든 아나그램을 찾는 문제로 문자열 S가  입력되고 특정 문자열 T가 입력되면, 문자열 S 안에 T와 아나그램이 되는 부분들을 찾고 그 개수를 출력하는 문제이다.

 

문제 해결

 

먼저 스캐너 객체를 생성해준 후 전체 문자열 fullStr와 아나그램인지 비교할 문자열 partStr 객체를 입력받아준다.

Scanner in = new Scanner(System.in);
String fullStr = in.nextLine();
String partStr = in.nextLine();

 

 

입력받은 문자열에서 각각의 문자(알파벳)이 키가 되고, 그 키가 등장한 횟수가 값이 되어야 하므로  HashMap을 <Character,Integer>형으로 만들어준다. 

partStr을 문자열 형태로 입력받았으므로 toCharArray()과정을 거쳐준 후 맵에 문자와 등장 횟수를 저장해준다.

HashMap<Character,Integer> partMap = new HashMap<>();
for(char key : partStr.toCharArray()) {
    partMap.put(key, partMap.getOrDefault(key,0)+1);
}

 

for문을 돌며 아나그램을 찾아줄건데, 한 번에 partStr의 길이만큼 검사하며 한 칸씩 옮겨가므로 partStr 길이를 포함할 수 있을 때까지만 반복하면 된다. 

b a c a A a c b a

b a c a A a c b a

b a c a A a c b a

...

즉 fullStr의 길이 - partStr의 길이만큼 반복해서 검사해주면 된다.

for(int i = 0; i <= fullStr.length() - partStr.length(); i++){ //partStr 길이를 포함할 수 있는 만큼 반복
	...

 

현재 위치에서 partStr의 길이만큼을 탐색하면서, currentChar 변수에 fullStr에서 현재 위치에 있는 문자를 담아준다.

currentChar를 키로하고 등장 횟수를 증가시키며 map에 저장하는 코드이다.

for(int j = i; j < i + partStr.length(); j++) { //map 안에 partStr의 길이만큼 담아줌.
    char currentChar = fullStr.charAt(j);
    map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
}

 

그렇게 map에 저장을 한 후 만약 map에 들어있는 부분이 partMap과 동일하다면, 즉 아나그램이면 count를 증가시켜준다.  

if(map.equals(partMap)){
    count++;
}

 

최종 코드

 

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

public class P04_모든아나그램찾기 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String fullStr = in.nextLine();
        String partStr = in.nextLine();

        HashMap<Character,Integer> partMap = new HashMap<>();
        for(char key : partStr.toCharArray()) {
            partMap.put(key, partMap.getOrDefault(key,0)+1);
        }

        int count = 0;
        for(int i = 0; i <= fullStr.length() - partStr.length(); i++){ //partStr 길이를 포함할 수 있는 만큼 반복
            HashMap<Character, Integer> map = new HashMap<>();
            for(int j = i; j < i + partStr.length(); j++) { //map 안에 partStr의 길이만큼 담아줌.
                char currentChar = fullStr.charAt(j);
                map.put(currentChar, map.getOrDefault(currentChar, 0) + 1);
            }
            if(map.equals(partMap)){
                count++;
            }
        }
        System.out.println(count);
    }
}