섹션 4. HashMap, TreeSet (해쉬, 정렬지원 Set) 4. 모든 아나그램 찾기

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식

이번 문제는 HashMap, Sliding Window, Two Pointer 를 사용하여 푸는 문제이다.

---

설계과정

1. HashMap을 2개 선언한다.

2. 고정된 크기의 윈도우를 만든다.

• 고정된 크기를 구하는 방식은 아래와 같다.
• 1. 고정 크기보다 하나 작게 적용한다.(left pointer)
• 2. 적용하지 않았던 마지막 하나를 적용해 원하는 크기를 만든다.(right pointer)
• 3. left pointer가 증가해서 하나 빠지고, right pointer가 증가해서 하나 추가되는 방식으로 윈도우를 민다.
• 고정 크기의 슬라이딩 윈도우를 배울 때에 기본적으로 배우는 방식이다.

3. 두 HashMap을 비교한다.

4. 고정된 크기의 윈도우를 하나씩 밀면서 두 HashMap이 동일하면 결과 개수를 누적한다.

5. Value가 0인 Key는 제거한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int 형으로 메소드를 작성한다.

 

3. 결과값을 출력할  result와 두 개의 HashMap을 선언한다.

• mapA : mapB와 비교하기 위해 윈도우를 이동하며 값을 저장한다.
• mapB : T 문자열을 HashMap 형태로 저장한다.

4. mapB에 입력받은 문자열 word의 알파벳들(Key)과 해당 알파벳의 개수(Value)를 HaspMap에 넣는다.

• toCharArray() : 입력된 문자열을 문자 하나씩 분리해서 문자 배열을 생성한다.
• put() : Key와 Value 값을 HashMap에 넣는다. 만약 키 값이 없으면 생성한다.
• getOrDefault(Key, value) : 찾는 키가 존재한다면 그 값을 반환하고 없다면 기본 값을 반환하는 메소드이다.

mapB

5. 고정된 윈도우 크기에서 -1을 하여 left pointer를 mapA에 넣는다.

• L : 고정 크기보다 하나 작게 적용하기 위해 length()를 구한 후, 1을 뺀다.
• 0부터 L까지 돌면서 키가 있으면 1을 넣어준다.

mapA

6. lt 포인터를 0으로 초기화하고, rt 포인터를 L부터 전체 문자열의 길이만큼 증가시키며 mapA에 값을 넣는다.

mapA

7. equals() 를 사용하여 mapA와 mapB를 비교하고, 동일하면 결과값 변수인 result를 증가시킨다.

• A.equals(B) : A와 B가 동일한지 비교해서 true, false로 리턴한다. 이 때, Key와 Value가 모두 동일한 지를 확인한다.

8. 윈도우를 이동시키기 위해 lt 포인터에서 key의 value를 1 뺀다.

mapA

9. remove()를 사용하여 value가 0이 된 key를 제거한다.

• remove() : 배열에 값을 제거한다.

mapA

10. lt 값을 증가시키고, for문을 돌면서 결과값을 출력한다.

• 아래 그림을 통해 mapA의 변화 과정을 확인해보자.

---

전체 문자열

첫번째 mapA : key와 value가 동일하므로 result = 1

lt[0]에서 value -1

value가 0인 key 제거

두번째 mapA : lt 와 rt가 1씩 증가

lt[1]에서 value -1 > value가 0인 key 없으므로 유지

 

세번째 mapA :  lt 와 rt가 1씩 증가

lt[2]에서 value -1 > value가 0인 key 제거

네번째 mapA :  lt 와 rt가 1씩 증가

lt[3]에서 value -1 > value가 0인 key 없으므로 유지

다섯번째 mapA :  lt 와 rt가 1씩 증가

lt[4]에서 value -1 > value가 0인 key 제거

여섯번째 mapA :  key와 value가 동일하므로 result = 2

lt[5]에서 value -1 > value가 0인 key 제거

일곱번째 mapA :  key와 value가 동일하므로 result = 3

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원) 강의를 참고하여 작성하였습니다.