섹션 4. HashMap, TreeSet (해쉬, 정렬지원 Set) 3. 매출액의 종류

문제

• 현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를 각  구간별로 구하라고 했습니다.
• 만약 N=7이고 7일 간의 매출기록이 아래와 같고, 이때 K=4이면
• 20 12 20 10 23 17 10
• 각 연속 4일간의 구간의 매출종류는
• 첫 번째 구간은 [20, 12, 20, 10]는 매출액의 종류가 20, 12, 10으로 3이다.
• 두 번째 구간은 [12, 20, 10, 23]는 매출액의 종류가 4이다.
• 세 번째 구간은 [20, 10, 23, 17]는 매출액의 종류가 4이다.
• 네 번째 구간은 [10, 23, 17, 10]는 매출액의 종류가 3이다.
• N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별
• 매출액의 종류를 출력하는 프로그램을 작성하세요.

입력

• 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
• 두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력

• 첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다.

입출력 예제

---

풀이방식

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

---

설계과정

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

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

2. 고정된 크기의 윈도우를 하나씩 밀면서 HashMap에 Key와 Value를 저장한다.

3. HashMap의 크기를 구해서 결과 배열에 넣어 출력한다.

---

풀이과정

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

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

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

4. 입력받은 배열에서 인덱스가 0부터 K-1까지인 숫자들(Key)과 해당 숫자들의 개수(Value)를 HaspMap에 넣는다.

•  put() : Key와 Value 값을 HashMap에 넣는다. 만약 키 값이 없으면 생성한다.
• getOrDefault(Key, value) : 찾는 키가 존재한다면 그 값을 반환하고 없다면 기본 값을 반환하는 메소드이다.

---

아래 그림은 입력받은 배열이다.

다음은 0부터 K-1까지의 숫자와 개수를 HashMap에 넣은 결과이다.

K가 4라고 가정했을 때, 총 3개의 숫자가 선택되며 그에 대한 결과는 다음과 같다.

---

5. K-1부터 N까지 돌면서 윈도우를 움직이는 for문을 작성한다.

• lt : left pointer, 왼쪽 포인터를 의미한다.
• rt : right pointer, 오른쪽 포인터를 의미한다.

6. for 문을 돌면서 HashMap에 값을 넣는다.

• lt와 rt를 통해 윈도우 크기를 고정한다.
• [0 ~ K-1] for 문을 통해 K-1 만큼의 숫자(Key)와 개수(Value)를 HashMap에 넣고, [K-1 ~ N] for문을 통해 마지막 1개의 숫자와 개수를 HashMap에 넣는다.

---

 

[20, 12, 20, 10]

---

7. result에 HashMap의 크기를 넣는다. 위에 이미지를 예시로 들면 result에는 '3'이 들어간다.

• add() : 배열에 값을 넣는다.
• size() : 배열의 크기를 구한다.

8. arr[lt] 에서 1을 뺀 값을 lt에 넣는다.

• 윈도우가 이동하게 되면, arr[lt] 값이 사라지는 것이므로 해당 숫자의 개수를 1 빼준다.

---

[12, 20, 10, 23]

9. 만약 arr[lt] 값이 0이면 해당 숫자(Key)는 없다는 의미이므로 배열에서 제거한다.

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

10. 윈도우를 이동하기 위해 lt에 값을 더해준다.

 

수행 결과를 확인한다.

---

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