[JAVA] 모든 아나그램 찾기(Hash Map, sliding window)

1. 문제

- 설명

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

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

 

- 입력

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

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

 

- 출력

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

 

ex)

- 입력

bacaAacba
abc

 

- 출력

3 (bac, acb, cba)

 

2. HashMap

• 키(key) 값와 값(value)으로 구성된 Entity 객체를 저장하는 구조를 가지고 있다.
• 키와 값은 모두 객체이다.
• 키는 중복 저장 될수 없지만 값을 중복 저장 될 수 있다.
• HashMap<키 타입, 값 타입> = new HashMap<키 타입, 값 타입>();

키(KEY)

값(VALUE)

 

3. 설명

s문자열을 lt값은 0 rt값은 (T문자열 길이 -1) 지정한다. 

b	a	c	a	A	a	c	b	a
lt	rt

lt값과 rt값 사이에 있는 문자열을 sMap을 생성한다.

b	a
1	1

t문자열의 값은 char문자로 쪼개어서 tmap을 생성한다.

a	b	c
1	1	1

for 문을 돌려 rt값을 +1해주어 sMap에 추가 해준다.

b	a	c	a	A	a	c	b	a
lt		rt

sMap과 tmap이 같은지 비교 해준다. 같으면 결과값 answer값에 +1 해준다.

문자열 s의 길이만큼 lt값과 rt값을 증가시켜준다..

 

4. 코드

public int solution(String s, String t) {
    int answer = 0;//결과값
    HashMap<Character, Integer> sMap = new HashMap<>(); 
    HashMap<Character, Integer> tMap = new HashMap<>();
    int lt = 0;

    for (int i = 0; i<t.length()-1; i++){ 
        sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i),0)+1);
      //smap에 문자열 s를 char형으로 쪼개어 t의 문자열 -1 값을 너어준다.
      //map.getOrDefault -> value +1, value값이 없으면 0으로 설정하여 +1 해준다.
    }
   for (char c : t.toCharArray()){
       tMap.put(c, tMap.getOrDefault(c, 0)+1);
       //string 형 t를 char형으로 쪼개어 tMap 에 너어준다.
   }

    for (int rt = t.length()-1; rt<s.length(); rt++){
    // 위에서 sMap에 t-1만큼 너었으니 t-1부터 시작한다.
        sMap.put(s.charAt(rt), sMap.getOrDefault(s.charAt(rt),0)+1);
        //sMap에 string s의 rt에 있는 char형의 값을 너어준다.
        
        if (sMap.equals(tMap)) answer++;
        //smap과 tmap과 같으면 결과값을 +1 해준다.
        
        sMap.put(s.charAt(lt), sMap.getOrDefault(s.charAt(lt),0)-1);
        // 계속 비교를 위해 lt위치 값 sMap 에 빼준다.
        
        if (sMap.get(s.charAt(lt)) == 0) sMap.remove(s.charAt(lt));
        // 위에 lt위치에 있는 값을 빼주었는데 빼서 그 value값이 0이라면 sMap 에서 삭제 시킨다.
        
        lt++;
        //lt값을 1증가 시킨다.
    }
        return answer;
    }