섹션 4. HashMap, TreeSet - 4. 모든 아나그램 찾기

📌 문제 설명

S 문자열에서 T 문자열과 아나그램이 되는 부분 문자열의 개수를 구하는 문제입니다.

• 아나그램: 철자 구성과 개수가 같고, 순서만 다른 문자열
• 부분 문자열은 연속된 문자열이어야 합니다.
• 대소문자 구분

---

📝 입력 & 출력

입력

• 첫째 줄: S 문자열 (길이 ≤ 10,000)
• 둘째 줄: T 문자열 (길이 ≤ S 문자열)

출력

• 아나그램이 되는 부분 문자열의 개수 출력

---

🔸 예제 입력 & 출력

예제 입력 1

bacaAacba
abc

 

예제 출력 1

3

---

💡 해결 방법

• 슬라이딩 윈도우 + HashMap 비교를 사용하여 효율적으로 풀 수 있습니다.
• 윈도우 크기를 T 문자열 길이만큼 고정하고, 하나씩 옮겨가며 비교
• equals()로 두 HashMap이 같은지 비교

핵심 알고리즘

1. T 문자열을 기준으로 알파벳 개수 tMap 생성
2. S 문자열의 처음 (T 길이 - 1)개 문자로 sMap 초기화
3. 슬라이딩 윈도우 이동:
   • 새 문자 추가, 맨 왼쪽 문자 제거 (count 줄이고 0이면 remove)
   • sMap.equals(tMap) 이면 결과++

---

💻 코드 구현 (Java)

package partHashTree;

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

public class Problem4 {
	public int solution(String s, String t){
		int result=0;
		HashMap<Character, Integer> sMap = new HashMap<>();
		HashMap<Character, Integer> tMap = new HashMap<>();
		
		for(char x: t.toCharArray()) tMap.put(x, tMap.getOrDefault(x,0)+1);

		int k=t.length()-1;
		for(int i=0; i<k; i++) sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i),0)+1);				

		int lt=0;
		for(int rt=k; rt<s.length(); rt++) {
			sMap.put(s.charAt(rt), sMap.getOrDefault(s.charAt(rt),0)+1);
			if(tMap.equals(sMap)) result++;
			
			sMap.put(s.charAt(lt), sMap.get(s.charAt(lt))-1);
			if(sMap.get(s.charAt(lt))==0) sMap.remove(s.charAt(lt));
			lt++;
		}
		return result;
	}
	
	public static void main(String[] args) {
		Problem4 T = new Problem4();
		Scanner kb = new Scanner(System.in);
		String s = kb.next();
		String t = kb.next();
		
		System.out.print(T.solution(s, t));
		
		kb.close();
	}
}

 

---

📖 코드 설명

1️⃣ 기준 문자열의 빈도 기록

for(char x: t.toCharArray()) 
	tMap.put(x, tMap.getOrDefault(x, 0) + 1);

• 아나그램 판별 기준이 되는 t 문자열의 빈도수 저장

2️⃣ 윈도우 초기 세팅 (t 길이 - 1만큼)

for(int i = 0; i < t.length() - 1; i++) 
	sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);

• 슬라이딩 윈도우를 이동시키기 전 초기 sMap 구성

3️⃣ 슬라이딩 윈도우 탐색 시작

for(int rt = t.length() - 1; rt < s.length(); rt++) {
	sMap.put(s.charAt(rt), sMap.getOrDefault(s.charAt(rt), 0) + 1);
	if(sMap.equals(tMap)) result++;

• 새로운 문자 추가 후 tMap과 비교하여 아나그램 여부 판단

4️⃣ 윈도우 왼쪽 문자 제거

	sMap.put(s.charAt(lt), sMap.get(s.charAt(lt)) - 1);
	if(sMap.get(s.charAt(lt)) == 0) sMap.remove(s.charAt(lt));
	lt++;
}

• 윈도우에서 제외되는 문자 처리 (빈도 0이면 삭제)

---

⏳ 시간 복잡도 분석

• 윈도우를 이동하며 문자열 전체를 탐색 → O(N)
• 각 구간마다 map 비교는 최대 26개의 알파벳만 비교 → O(1)
• 총 시간 복잡도: O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런