[Ch.04 - HashTree] 04. 모든 아나그램 찾기 #

4. 모든 아나그램 찾기

 

설명

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

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

입력

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

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

출력

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

예시 입력 1 

bacaAacba
abc

예시 출력 1

3

 

---

 

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

public class Main {
	public int solution(String str, String s) {
		int answer=0;
		HashMap<Character, Integer> map = new HashMap<>();
		HashMap<Character, Integer> map2 = new HashMap<>();
		for(int i=0;i<s.length();i++) {
			map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)+1);
		}
		int lt=0;
		for(int rt=0;rt<str.length();rt++) {
			
			map2.put(str.charAt(rt), map2.getOrDefault(str.charAt(rt), 0)+1);
			
			
			if(map.equals(map2)) {
				answer++;
			}
			while(map2.size()>=map.size()) {
				map2.put(str.charAt(lt), map2.get(str.charAt(lt))-1);
				if(map2.get(str.charAt(lt))==0)
					map2.remove(str.charAt(lt));
				if(map.equals(map2)) {
					answer++;
				}
				lt++;
			}
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str = kb.next();
		String s = kb.next();
		System.out.println(T.solution(str, s));
	}

}

-> 틀린 테스트케이스 존재

: s의 길이 전까지 세팅 후, rt가 돌도록

 

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

public class Main {
	public int solution(String str1, String str2) {
		int answer=0;
		HashMap<Character, Integer> map1 = new HashMap<>();

		for(int i=0;i<str2.length();i++) {
			map1.put(str2.toCharArray()[i], map1.getOrDefault(str2.toCharArray()[i], 0)+1);
		}
		for(int i=0;i<=str1.length()-str2.length();i++) {
			HashMap<Character, Integer> map2 = new HashMap<>();
			for(int j=i;j<i+str2.length();j++) map2.put(str1.toCharArray()[j], map2.getOrDefault(str1.toCharArray()[j], 0)+1);
			
			if(map1.equals(map2)) answer++;
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Main T =new Main();
		Scanner kb =new Scanner(System.in);
		
		String str1= kb.next();
		String str2= kb.next();
		System.out.println(T.solution(str1, str2));
		
	}

}

-> Timelimit 발생

->처음 값 제외하고 다음 값 추가하는 방식으로 변경

 

 

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

public class Main {
	public int solution(String str1, String str2) {
		int answer = 0;
		HashMap<Character, Integer> map1 = new HashMap<>();

		for (int i = 0; i < str2.length(); i++) {
			map1.put(str2.toCharArray()[i], map1.getOrDefault(str2.toCharArray()[i], 0) + 1);
		}

		HashMap<Character, Integer> map2 = new HashMap<>();
		for (int i = 0; i < str2.length(); i++) {
			map2.put(str1.toCharArray()[i], map2.getOrDefault(str1.toCharArray()[i], 0) + 1);
			
			if (map1.equals(map2))
				answer++;
		}

		for (int j = 0; j <str1.length() - str2.length(); j++) {
			map2.put(str1.toCharArray()[j], map2.get(str1.toCharArray()[j]) - 1);
			if (map2.get(str1.toCharArray()[j]) == 0)
				map2.remove(str1.toCharArray()[j]);

			map2.put(str1.toCharArray()[j+str2.length()], map2.getOrDefault(str1.toCharArray()[j+str2.length()], 0) + 1);

			if (map1.equals(map2))
				answer++;
		}

		return answer;
	}

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

		String str1 = kb.next();
		String str2 = kb.next();
		System.out.println(T.solution(str1, str2));

	}

}

 

 

 

+) 세련된 풀이

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

public class Main {
	public int solution(String a, String b) {
		int answer=0;
		HashMap<Character, Integer> am = new HashMap<>();
		HashMap<Character, Integer> bm = new HashMap<>();
		for(char x: b.toCharArray()) bm.put(x, bm.getOrDefault(x, 0)+1);
		//character
		
		//b길이 전까지 돌고, rt이후부터 돈다 : 0, 1까지
		int L=b.length()-1;
		for(int i=0;i<L;i++) am.put(a.charAt(), am.getOrDefault(a.charAt(i), 0)+1);
		//키
		
		
		//Two pointer
		int lt=0;
		for(int rt=L; rt<a.length(); rt++) {
			am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0)+1);
			
			if(am.equals(bm)) answer++;
			am.put(a.charAt(lt), am.get(a.charAt(lt))-1);
			
			if(am.get(a.charAt(lt))==0) am.remove(a.charAt(lt));
			lt++;
		}
		
		
		return answer;
		
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		
		String a=kb.next();
		String b=kb.next();
		System.out.println(T.solution(a,b));
	}

}

 

 

(1) 비교할 문자열 길이만큼, map에 삽입 -> 같은지 확인

(2) 다음 문자 추가, 첫 문자 제거 후, 개수가 0개인것 제거-> 같은지 확인

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1 = in.next();
    String str2 = in.next();
    System.out.println(solution(str1, str2));
  }
  static int solution(String str1, String str2){
    int n=str2.length();
    int answer=0;
    Map<Character, Integer> map = new HashMap<>();
    Map<Character, Integer> map2 = new HashMap<>();
    
    char[] arr = str1.toCharArray();
    char[] arr2 = str2.toCharArray();
    for(int i=0;i<n;i++){
      map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
      map2.put(arr2[i], map2.getOrDefault(arr2[i], 0)+1);
    }

    if(map.equals(map2)) answer++;
    
    for(int i=n;i<str1.length();i++){
      map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
      map.put(arr[i-n],map.get(arr[i-n])-1);
      if(map.get(arr[i-n])==0) map.remove(arr[i-n]);
      if(map.equals(map2))answer++;
    }

    return answer;
  }
}

---

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1= in.next();
    String str2= in.next();
    System.out.println(Solution(str1, str2));
  }
  private static int Solution(String str1, String str2){
    int answer=0;
    int n=str1.length();
    int m=str2.length();
    Map<Character,Integer> map1 = new HashMap<>();
    Map<Character,Integer> map2 = new HashMap<>();
    
    for(int i=0;i<m; i++){
      map1.put(str1.charAt(i), map1.getOrDefault(str1.charAt(i), 0)+1);
      map2.put(str2.charAt(i), map2.getOrDefault(str2.charAt(i), 0)+1);
    }
    if(map1.equals(map2))answer+=1;
    for(int i=1; i<n-m+1; i++){
      map1.put(str1.charAt(i-1), map1.getOrDefault(str1.charAt(i-1), 0)-1);
      if(map1.get(str1.charAt(i-1))==0)map1.remove(str1.charAt(i-1));
      
      map1.put(str1.charAt(i+m-1), map1.getOrDefault(str1.charAt(i+m-1), 0)+1);
      if(map1.equals(map2))answer+=1;
    }
    
    return answer;
  }
}