[PS] 인프런 강의 - HashMap, HashSet, TreeSet 4. 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

 

문제

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

▣ 입력설명
첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

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

▣ 입력예제 1
bacaAacba
abc

▣ 출력예제 1
3
출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

▣ 입력예제 2
bacaAacbaa
abca

▣ 출력예제 2
3

 

풀이

앞에서 푼 문제 아나그램 + 매출액 종류 문제를 합친?문제인 듯 하다.

간단한 문제인데 좀 붙잡고 있었다. 요즘 왜이렇게 머리가 안돌아가는 지 모르겠다...

 

코드

1) 내 풀이

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

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		String s = in.next();
		String t = in.next();
		//s에서 t와 아나그램이 되는 s의 연속부분문자열 개수(대소문자 구분)
		//문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램
		HashMap<Character, Integer> tMap = new HashMap<>();
		
		for(char c : t.toCharArray()) {
			tMap.put(c, tMap.getOrDefault(c, 0)+1);
		} //t를 해쉬에 저장
		
		//t의 길이만큼 sliding window
		int lt = 0;
		int answer = 0;
		HashMap<Character, Integer> sMap = new HashMap<>(); 
		
		for(int rt=0; rt<s.length(); rt++) {
			sMap.put(s.charAt(rt), sMap.getOrDefault(s.charAt(rt), 0)+1); //맵에 추가
					
			if(rt-lt+1 == t.length()) { //꽉차면 비교 & lt 땡김
				if(sMap.equals(tMap)) answer++;
				//땡겼으니까 checkMap에서 빼기
				sMap.put(s.charAt(lt), sMap.get(s.charAt(lt))-1);
				if(sMap.get(s.charAt(lt)) == 0) sMap.remove(s.charAt(lt)); //값이 0이면 맵에서 삭제
				lt++;
			}
		}
		
		System.out.print(answer);
		
		
	}
}

 

2) 강사님 풀이

import java.util.*;
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);
		int L=b.length()-1;
		for(int i=0; i<L; i++) am.put(a.charAt(i), am.getOrDefault(a.charAt(i), 0)+1);
		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.print(T.solution(a, b));
	}
}