자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 모든 아나그램 찾기

 

https://hyejin.tistory.com/1229

자바 알고리즘 문제 풀이 입문. 섹션4. HashMap, TreeSet (해쉬, 정렬지원 Set) : 매출액의 종류

-> 이전 문제 풀이 

 

 

4. 모든 아나그램 찾기 

설명

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

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

 

입력

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

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

 

출력

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

 

예시 입력 1 

bacaAacba
abc

 

예시 출력 1

3

 

힌트

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

 

 

문제 풀이 1

public int solution(String s, String t)
{
   int answer = 0;
   HashMap<Character, Integer> map = new HashMap<>();
   HashMap<Character, Integer> map2 = new HashMap<>();
   char[] chars = s.toCharArray();
   
   for (int i = 0; i< t.length() - 1 ; i++)
   {
      map.put(chars[i], map.getOrDefault(chars[i], 0) + 1);
   }
   
   for (char c : t.toCharArray())
   {
      map2.put(c, map2.getOrDefault(c, 0) + 1);
   }
   
   
   int lt = 0;
   for (int i = t.length() -1; i< chars.length; i++)
   {
      int cnt = 0;
      map.put(chars[i], map.getOrDefault(chars[i], 0) + 1);
      for (char c : t.toCharArray())
      {
         if (map.containsKey(c)) {
            if (map.get(c) == map2.get(c)) {
               cnt++;
            } else {
               break;
            }
         } else
         {
            break;
         }
      }
      if (cnt == t.length())
      {
         answer++;
      }
      
      map.put(chars[lt], map.get(chars[lt]) - 1);
      if (map.get(chars[lt]) == 0) {
         map.remove(chars[lt]);
      }
      lt++;
   }
   
   
   return answer;
}

👩‍💻 : 이 문제는 저번 문제 풀이랑 거의 비슷하게 풀면 된다. 

먼저 String s의 문자 배열을 통해 map에 문자를 key로 그리고 그 개수를 value로 담아준다. (첫 세팅을 하는 것이기 때문에 t  문자열 길이 -1 까지만 map에 우선 넣어준다. -> 반복문을 돌면서 Sliding Window 알고리즘 적용할 것이기 때문) 

다음 map2 에는  String t 문자 배열을 담아준다. 

 

다음 for문을 통해 t문자열 길이 - 1 부터 시작해서 주어진 문자열 S의 길이까지 반복문을 돌면서 

우선 map에 chars[i]의 값을 key 값으로 getOrDefault를 통해 값이 없으면 0 + 1 아니면 value + 1 하도록 해준다. 

 

그러면 일단 t 문자열 길이만큼 map에 넣어줬기 때문에 t 문자열과 비교를 해서 아나그램인지 먼저 비교해야 한다. 

그러기 위해서 

for (char c : t.toCharArray())
{
   if (map.containsKey(c)) {
      if (map.get(c) == map2.get(c)) {
         cnt++;
      } else {
         break;
      }
   } else
   {
      break;
   }
}

반복문을 돌면서 map에 c 문자가 key로 있는지 확인하고 map.get(c)와 map2.get(c)가 같으면 임의의 변수 cnt의 값을 +1 을 해준다. key 가 없다는 말은 아나그램이 아니기 때문에 break로 해당 반복문을 빠져 나오고, map.get(c) 와 map2.get(c)가 같지 않을 때도 key의 개수가 다르다는 것이므로 아나그램이 아니다. 

 

반복문을 모두 다 돌고 cnt의 값이 t문자열의 길이와 같으면 answer에 +1 을 해준다. ( 아나그램이라는 뜻!) 

(key가 map에 모두 포함되어 있고, 개수도 같다는 것이기 때문 ! ) 

 

이렇게 answer에 +1 해주고 나면 이제 다음 문자로 넘어가야 하기 때문에 그 전의 값 (제일 첫번째 값)은 제거해줘야 한다. 

map.put(chars[lt], map.get(chars[lt]) - 1);
if (map.get(chars[lt]) == 0) {
   map.remove(chars[lt]);
}
lt++;

lt를 기준으로 map에서 값을 꺼내 -1 해주고, 이 값이 만약 0 이면 이제 key 값도 remove 해준다. 

그 다음 lt 를 +1 해준다. (그래야 슬라이딩 윈도우로 옆으로 넘어가면서 윈도우를 만들 수 있기 때문 !!) 

 

 

나는 equals로 HashMap을 비교할 생각을 못해서 이렇게 반복문으로 key가 있는지 확인하고 get 해서 value값을 비교해준 것이다.. equals 사용하면 

for (char c : t.toCharArray())
{
   if (map.containsKey(c)) {
      if (map.get(c) == map2.get(c)) {
         cnt++;
      } else {
         break;
      }
   } else
   {
      break;
   }
}
if (cnt == t.length())
{
   answer++;
}

이 부분을 제거할 수 있다.... ㅎ 

 

 

문제 풀이 2

public int solution2(String a, String b)
{
   int answer = 0;
   HashMap<Character, Integer> am = new HashMap<>();
   HashMap<Character, Integer> bm = new HashMap<>();
   
   for (char c : b.toCharArray())
   {
      bm.put(c, bm.getOrDefault(c, 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;
}

👾 : 강사님도 나와 풀이 방식은 동일한데 여기서 강사님은 HashMap의 equals를 사용해서 am과 bm을 비교해줬다. 

am은 주어진 문자열 a의 대해 문자 배열로 만들어서 b 문자열의 개수 -1 전까지만 Map의 Key, 그리고 value (key 의 개수)를 저장해줬다. (슬라이딩 윈도우로 옆으로 점점 추가하면서 갈 것이기 때문!) 

bm은 주어진 문자열 b의 문자 배열에 대해서 Map의 Key, 그리고 value (key 의 개수)를 저장해줬다. 

HashMap<Character, Integer> am = new HashMap<>();
HashMap<Character, Integer> bm = new HashMap<>();

for (char c : b.toCharArray())
{
   bm.put(c, bm.getOrDefault(c, 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);
}

 

그 다음에는 이제 lt, rt 를 이용해서 

먼저 for문 반복문으로 rt는 a 문자열 길이까지 쭉쭉 옆으로 한칸씩 넘어간다. 

am에 put을 a.charAt(rt) 를 key 값으로 하는 value가 있으면 그 value에 +1 아니면 0 +1 해준다. 

 

다음 am과 bm 을 eqauls로 비교해서 둘이 같다면 아나그램이라는 뜻이기 때문에 answer + 1 해준다. 

am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0) + 1);

if (am.equals(bm))
{
   answer++;
}

 

그 다음 이제 rt 가 옆으로 가기전에 lt의 값을 빼줘야 하기 때문에 map.get(a.charAt(lt))의 value 값을 구해서 -1 해준다. 

그 다음 이 key 값의 value가 0 이면 해당 문자가 윈도우에서 없다는 뜻이기 때문에 am 에서 remove 해줘야 한다.

그 다음 lt 값을 +1 증가 시켜주면 된다. 

 

 

 

😵 슬라이딩 윈도우는 차근 차근 생각해보면 그렇게 엄청 어려운 난이도의 문제는 아닌 것 같다. 

lt ,  rt 와 함께 하나씩 옆으로 밀면서 추가하고 비교하고 삭제하고 이 과정을 생각하면 된다 !