JAVA 알고리즘 문제 - 모든 아나그램 찾기

모든 아나그램 찾기

 

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.

 

설명

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

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

 

입력

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

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

 

출력

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

 

입력예제

bacaAacba
abc

 

출력예제

3

 

전체코드

package Level1;

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

public class Main {
	
	public int test(String a, String b) {
		int answer= 0;
		HashMap<Character, Integer> amap = new HashMap();
		HashMap<Character, Integer> bmap = new HashMap();
		
		for(char x : b.toCharArray()) {
			bmap.put(x, bmap.getOrDefault(x, 0) +1);
		}
		
		int L = b.length()-1;
		
		for(int i=0; i<L; i++) {
			amap.put(a.charAt(i), amap.getOrDefault(a.charAt(i), 0)+1);
		}
		
		int lt =0;
		for(int rt = L; rt<a.length(); rt++) {
			amap.put(a.charAt(rt), amap.getOrDefault(a.charAt(rt), 0)+1);
			
			if(amap.equals(bmap)) {
				answer ++;
			}
			amap.put(a.charAt(lt), amap.get(a.charAt(lt))-1);
			if(amap.get(a.charAt(lt))==0) amap.remove(a.charAt(lt));
			lt++;
		}
		
		
		return answer;
	}
	
	public static void main(String[] args){
		Main t = new Main();
		Scanner kb = new Scanner(System.in);
		
		String S = kb.next();
		String T = kb.next();
		
		System.out.println(t.test(S, T));
    }
}

---

이 문제역시 sliding window 방식으로 해결을 하려고한다. 

		int answer= 0;
		HashMap<Character, Integer> amap = new HashMap();
		HashMap<Character, Integer> bmap = new HashMap();

우선 입력받은 문자열을 담아 비교할 amap, bmap을 생성하고 이를 비교했을경우 아나그램인경우를 카운트할 answer를 선언해준다.

 

		for(char x : b.toCharArray()) {
			bmap.put(x, bmap.getOrDefault(x, 0) +1);
		}

우선 입력받은 b 문자열을 bmap에 모두 담아준다. (abc입력받음)

Key	Value
a	1
b	1
c	1

이와같은 형태의 map이 만들어진다.

 

그런후에 입력받은 a 문자열을 담으려고하는데 b의 길이와 같은지 비교하기 위해 우선 b.length()-1로 설정하고 해당 길이만큼 amap에 a문자열을 담아준다. (입력받은 a문자열 bacaAacba)

		int L = b.length()-1;
		
		for(int i=0; i<L; i++) {
			amap.put(a.charAt(i), amap.getOrDefault(a.charAt(i), 0)+1);
		}

Key	Value
b	1
a	1

 

그리고 난 뒤 sliding window방식으로 두개의 포인터를 지정해 일정한 사이즈로 옮겨가며 해당값을 비교하려고한다.

		int lt =0;
		for(int rt = L; rt<a.length(); rt++) {
			amap.put(a.charAt(rt), amap.getOrDefault(a.charAt(rt), 0)+1);
			
			if(amap.equals(bmap)) {
				answer ++;
			}
			amap.put(a.charAt(lt), amap.get(a.charAt(lt))-1);
			if(amap.get(a.charAt(lt))==0) amap.remove(a.charAt(lt));
			lt++;
		}

하나씩 그림을 그려가며 풀어보겠다

아래의 표는 입력받은 a 의 index와 해당 값이다.

0	1	2	3	4	5	6	7	8
b	a	c	a	A	a	c	b	a

 

1. lt = 0 / rt = 2

 

amp에 c요소를 추가 

Key	Value
b	1
a	1
c	1

bamp과 key와 value값이 일치 answer ++

 

 

amap.put(a.charAt(lt), amap.get(a.charAt(lt))-1);   ===> 해당되는 Key : b 의 값을 -1

Key	Value
b	0
a	1
c	1

 

if(amap.get(a.charAt(lt))==0) amap.remove(a.charAt(lt));

Value의 값이 =0 이라면 해당 값 삭제 ==> (b,0)삭제 

Key	Value
a	1
c	1

---

2. lt = 1 / rt = 3

 

amap.put(a.charAt(rt), amap.getOrDefault(a.charAt(rt), 0)+1);  ===> amp에 A요소 추가

Key	Value
a	1
c	1
A	1

bmap과 값이 일치하지 않기때문에 answer은 증가되지 않음

 

amap.put(a.charAt(lt), amap.get(a.charAt(lt))-1);   ===> 해당되는 Key : a 의 값을 -1

Key	Value
a	0
c	1
A	1

 

if(amap.get(a.charAt(lt))==0) amap.remove(a.charAt(lt));

Value의 값이 =0 이라면 해당 값 삭제 ==> (c,0)삭제 

Key	Value
c	1
A	1

---

3. lt = 2 / rt = 4

 

amap.put(a.charAt(rt), amap.getOrDefault(a.charAt(rt), 0)+1);  ===> amp에 A요소 추가

Key	Value
c	1
A	1
a	1

bmap과 값이 일치하지 않기때문에 answer은 증가되지 않음

 

amap.put(a.charAt(lt), amap.get(a.charAt(lt))-1);   ===> 해당되는 Key : c 의 값을 -1

Key	Value
c	0
A	1
a	1

 

if(amap.get(a.charAt(lt))==0) amap.remove(a.charAt(lt));

Value의 값이 =0 이라면 해당 값 삭제 ==> (c,0)삭제 

Key	value
A	1
a	1

 

---

이와같이 반복한다면 총 answer의 값은 3이 출력된다.