programmers) 할인 행사

할인 행사 - 고정길이 슬라이딩 윈도우로 풀기

문제를 풀게 된 이유

슬라이딩 윈도우를 공부한 뒤, 실제 문제에 적용해보기 위해 프로그래머스의 할인 행사 문제를 풀어봤다.

이 문제는 10일 동안 할인하는 상품 목록을 확인해서, 내가 원하는 상품과 수량을 모두 구매할 수 있는 회원가입 날짜의 개수를 구하는 문제다.

처음 문제를 봤을 때는 단순히 10일씩 잘라서 확인하면 될 것 같았다.
하지만 직접 코드를 작성해보니, 단순 반복보다 고정길이 슬라이딩 윈도우로 푸는 게 더 깔끔하다는 걸 알게 됐다.

---

문제 이해

회원가입을 하면 가입한 날부터 10일 동안 할인 상품을 구매할 수 있다.

예를 들어 내가 원하는 상품이 다음과 같다고 하자.

want = ["banana", "apple", "rice", "pork", "pot"];
number = [3, 2, 2, 2, 1];

이 뜻은 10일 동안 아래 상품을 모두 구매할 수 있어야 한다는 의미다.

banana 3개
apple 2개
rice 2개
pork 2개
pot 1개

즉, 할인 목록에서 연속된 10일 구간을 확인했을 때, 그 안의 상품 구성이 내가 원하는 상품 구성과 정확히 같아야 한다.

---

처음 생각한 접근

처음에는 단순하게 이런 방식으로 접근하려고 했다.

0일부터 9일까지 확인
1일부터 10일까지 확인
2일부터 11일까지 확인
...

즉, 모든 시작 날짜마다 10일치를 다시 세는 방식이다.

for (int start = 0; start <= discount.length - 10; start++) {
    // start부터 start + 9까지 상품 개수 확인
}

이 방식도 풀 수는 있다.

하지만 매번 10일치를 새로 세는 것보다, 이미 계산한 10일 구간에서 빠지는 상품 하나와 새로 들어오는 상품 하나만 갱신하는 방식이 더 자연스럽다고 생각했다.

그래서 슬라이딩 윈도우로 풀기로 했다.

---

슬라이딩 윈도우로 생각하기

이 문제의 핵심은 10일 구간이 고정되어 있다는 점이다.

처음 구간은 다음과 같다.

discount[0] ~ discount[9]

다음 구간은 다음과 같다.

discount[1] ~ discount[10]

이때 모든 상품을 다시 셀 필요는 없다.

바뀌는 것은 딱 두 개다.

빠지는 상품: discount[0]
들어오는 상품: discount[10]

그래서 현재 10일 구간의 상품 개수를 HashMap으로 관리하고, 윈도우가 이동할 때마다 상품 개수만 갱신하면 된다.

---

사용한 자료구조

이번 문제에서는 HashMap 두 개를 사용했다.

Map<String, Integer> wantMap = new HashMap<>();
Map<String, Integer> windowMap = new HashMap<>();

각 Map의 역할은 다음과 같다.

Map	역할
wantMap	내가 원하는 상품과 수량 저장
windowMap	현재 10일 구간의 상품과 수량 저장

예를 들어 wantMap은 이런 형태가 된다.

banana = 3
apple = 2
rice = 2
pork = 2
pot = 1

그리고 현재 10일 구간의 상품 개수도 windowMap에 같은 방식으로 저장한다.

두 Map이 같으면, 해당 날짜에 회원가입했을 때 원하는 상품을 모두 살 수 있다는 뜻이다.

if (wantMap.equals(windowMap)) {
    answer++;
}

HashMap.equals()는 key와 value가 모두 같을 때 true를 반환한다.

---

풀이 과정

1. 원하는 상품 정보를 Map에 저장

먼저 want와 number 배열을 이용해 원하는 상품 정보를 저장한다.

for (int i = 0; i < want.length; i++) {
    wantMap.put(want[i], number[i]);
}

---

2. 첫 10일 구간 만들기

그다음 할인 목록의 처음 10일을 확인해서 windowMap을 만든다.

for (int i = 0; i < 10; i++) {
    windowMap.put(discount[i], windowMap.getOrDefault(discount[i], 0) + 1);
}

여기서 getOrDefault()를 사용했다.

windowMap.getOrDefault(discount[i], 0)

해당 상품이 이미 있으면 기존 개수를 가져오고, 없으면 0을 가져온다.
그래서 처음 등장하는 상품도 자연스럽게 1개로 저장할 수 있다.

---

3. 첫 번째 구간 확인

처음 만든 10일 구간도 정답 후보이므로 반드시 확인해야 한다.

if (wantMap.equals(windowMap)) {
    answer++;
}

처음에는 이 부분이 왜 필요한지 헷갈렸다.

하지만 반복문을 right = 10부터 시작하면, 반복문 안에서 처음 확인하는 구간은 discount[1] ~ discount[10]이 된다.

즉, 첫 번째 구간인 discount[0] ~ discount[9]는 반복문 전에 따로 확인해야 한다.

---

4. 윈도우 이동하기

이후에는 10일 구간을 하루씩 이동한다.

for (int right = 10; right < discount.length; right++) {
    int left = right - 10;
}

여기서 right는 새로 들어오는 상품의 위치이고, left는 빠지는 상품의 위치다.

예를 들어 right = 10이면,

이전 구간: 0 ~ 9
다음 구간: 1 ~ 10

빠지는 위치는 0이다.

left = right - 10;
left = 10 - 10 = 0;

---

5. 빠지는 상품 제거

윈도우가 이동하면 왼쪽 상품이 빠지므로 개수를 1 줄인다.

String removeItem = discount[left];

windowMap.put(removeItem, windowMap.get(removeItem) - 1);

그리고 개수가 0이 되면 Map에서 제거한다.

if (windowMap.get(removeItem) == 0) {
    windowMap.remove(removeItem);
}

이 부분도 중요했다.

처음에는 개수가 0이면 그냥 둬도 되지 않나 생각했다.
하지만 HashMap.equals()로 비교할 때, 0개인 상품이 key로 남아 있으면 다른 Map으로 판단된다.

예를 들어 아래 두 Map은 같지 않다.

wantMap = {
    apple = 1,
    banana = 1
}

windowMap = {
    apple = 1,
    banana = 1,
    rice = 0
}

rice가 0개라도 key가 존재하기 때문에 equals() 결과는 false가 된다.

그래서 개수가 0이 된 상품은 반드시 제거해야 한다.

---

6. 들어오는 상품 추가

오른쪽에서 새로 들어오는 상품은 개수를 1 증가시킨다.

String addItem = discount[right];

windowMap.put(addItem, windowMap.getOrDefault(addItem, 0) + 1);

새로 들어오는 상품이 기존에 없을 수도 있으므로, 여기서도 getOrDefault()를 사용해야 한다.

---

최종 코드

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {

        int answer = 0;

        Map<String, Integer> wantMap = new HashMap<>();
        Map<String, Integer> windowMap = new HashMap<>();

        // 원하는 상품과 수량 저장
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }

        // 첫 10일 구간의 상품과 수량 저장
        for (int i = 0; i < 10; i++) {
            windowMap.put(discount[i], windowMap.getOrDefault(discount[i], 0) + 1);
        }

        // 첫 번째 10일 구간 확인
        if (wantMap.equals(windowMap)) {
            answer++;
        }

        // 10일짜리 윈도우를 하루씩 이동
        for (int right = 10; right < discount.length; right++) {
            int left = right - 10;

            String removeItem = discount[left];
            String addItem = discount[right];

            // 왼쪽에서 빠지는 상품 개수 감소
            windowMap.put(removeItem, windowMap.get(removeItem) - 1);

            // 개수가 0이면 Map에서 제거
            if (windowMap.get(removeItem) == 0) {
                windowMap.remove(removeItem);
            }

            // 오른쪽으로 새로 들어오는 상품 개수 증가
            windowMap.put(addItem, windowMap.getOrDefault(addItem, 0) + 1);

            // 현재 10일 구간이 원하는 상품 구성과 같은지 확인
            if (wantMap.equals(windowMap)) {
                answer++;
            }
        }

        return answer;
    }
}

---

내가 헷갈렸던 부분

1. 첫 번째 구간을 왜 따로 확인해야 하는지

처음 10일 구간을 만든 뒤 바로 확인하는 코드가 필요했다.

if (wantMap.equals(windowMap)) {
    answer++;
}

반복문이 right = 10부터 시작하기 때문에, 반복문 안에서는 이미 두 번째 구간부터 검사하게 된다.

그래서 첫 번째 구간인 0 ~ 9는 따로 확인해야 한다.

---

2. containsKey()를 잘못 사용함

처음에는 첫 10일 구간을 만들 때 이런 식으로 작성했다.

if (windowMap.containsKey(discount[i])) {
    windowMap.put(discount[i], windowMap.getOrDefault(discount[i], 0) + 1);
}

하지만 처음 windowMap은 비어 있다.

그래서 containsKey()가 항상 false가 되고, 아무 상품도 Map에 들어가지 않는다.

이 경우에는 조건문 없이 바로 넣어야 한다.

windowMap.put(discount[i], windowMap.getOrDefault(discount[i], 0) + 1);

---

3. Map 타입을 잘못 선언함

처음에는 Map 타입을 잘못 선언했다.

Map<String, String> wantMap = new HashMap<>();

상품 이름은 String이 맞지만, 상품 개수는 숫자이므로 Integer가 맞다.

Map<String, Integer> wantMap = new HashMap<>();

이런 기본적인 타입 실수도 조심해야겠다고 느꼈다.

---

4. getOrDefault() 사용법을 헷갈림

Java에서 Map.get()은 기본값을 받을 수 없다.

처음에는 아래처럼 쓰려고 했다.

windowMap.get(discount[i], 0);

하지만 Java에서는 이런 문법이 없다.

기본값이 필요할 때는 getOrDefault()를 사용해야 한다.

windowMap.getOrDefault(discount[i], 0);

---

5. 개수가 0이 된 상품을 제거해야 한다는 점

이 부분은 문제를 풀면서 가장 기억에 남았다.

개수가 0이 된 상품을 Map에 남겨두면, 실제로는 없는 상품인데도 key가 남아 있는 상태가 된다.

그래서 equals() 비교가 실패할 수 있다.

if (windowMap.get(removeItem) == 0) {
    windowMap.remove(removeItem);
}

Map끼리 비교할 때는 key까지 정확히 같아야 한다는 점을 다시 확인할 수 있었다.

---

시간복잡도

할인 목록의 길이를 N이라고 하면, 할인 목록을 한 번 순회하면서 윈도우를 이동한다.

시간복잡도: O(N)

각 구간마다 HashMap.equals()를 사용하지만, want의 길이는 크지 않기 때문에 부담이 크지 않다.

공간복잡도는 현재 구간의 상품 개수를 저장하는 Map과 원하는 상품 Map을 사용하므로 다음과 같다.

공간복잡도: O(상품 종류 수)

---

정리

프로그래머스 할인 행사 문제는 고정길이 슬라이딩 윈도우 + HashMap 카운팅 문제였다.

처음에는 단순히 10일씩 다시 세면 된다고 생각했지만, 슬라이딩 윈도우로 접근하니 더 깔끔하게 풀 수 있었다.

이번 문제에서 핵심은 다음과 같다.

1. 10일 구간을 하나의 윈도우로 본다.
2. 처음 10일 구간을 먼저 만든다.
3. 첫 구간도 정답 후보로 확인한다.
4. 윈도우를 한 칸씩 이동하면서 빠지는 상품과 들어오는 상품만 갱신한다.
5. 현재 구간의 상품 개수가 원하는 상품 개수와 같으면 정답을 증가시킨다.

이번 문제를 풀면서 슬라이딩 윈도우를 실제 코드로 어떻게 적용하는지 조금 더 감이 잡혔다.

특히 단순 합이 아니라 상품 개수를 관리해야 하는 문제에서는 HashMap을 함께 사용하면 된다는 점을 배웠다.

다음에 비슷한 문제를 만나면 먼저 이렇게 생각해볼 것 같다.

구간 길이가 고정되어 있는가?
현재 구간에서 어떤 정보를 유지해야 하는가?
윈도우가 이동할 때 빠지는 값과 들어오는 값은 무엇인가?

이 문제는 슬라이딩 윈도우를 처음 연습하기에 좋은 문제였다.