Skip to main content

[Java] 131127 할인행사

📝 할인행사

1. 문제 요약

  • 회원이 원하는 제품(want[]) 과 그 수량(number[]) 이 주어진다.
    • 예: want = ["banana", "apple"], number = [3, 2]
      → 바나나 3개, 사과 2개를 원한다는 뜻
  • 마트에서 할인하는 품목이 날짜별로 순서대로 배열(discount[]) 로 주어진다.
    • 예: discount = ["chicken", "apple", "banana", "banana", "banana", "apple", ...]
  • 회원은 10일 연속으로 마트에서 장을 본다.
    • 즉, discount 배열에서 연속된 10일 구간을 하나 선택한다.
  • 이 10일 구간 안에서 회원이 원하는 제품을 원하는 수량 이상 구매할 수 있으면 성공이다.
  • 가능한 시작 날짜가 몇 개인지를 반환한다.

2. 접근 방식

  1. HashMap인 wantMap 선언하고 (상품 → 개수) 형태로 저장하기
  2. 10일 단위로 구간 검사 (슬라이딩 윈도우)
    • discount[]를 에서 연속된 10일씩 자르기
    • HashMap인 discountMap 선언하고 현재 구간 상품 카운팅
    • wantMap과 discountMap 비교
      • boolean valie 선언하고 true로 설정
      • wantMap에 있는 모든 key에 대해, discountMap의 수량이 부족하면 실패
      • 조건 다 맞으면 answer++
  3. answer을 리턴한다.

3. 정답코드

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        // HashMap에 원하는 제품, 수량 담기
        HashMap<String, Integer> wantMap = new HashMap<>(); 
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }
        
        // 해시맵에 discount를 10일씩 잘라서 discountMap 에 저장하기
        // wantMap이랑 비교하기 어떻게 짜지...
        
        // Sliding Window
        for (int i = 0; i <= discount.length - 10; i++) {
            HashMap<String, Integer> discountMap = new HashMap<>();
            
            // 1부터 10개 물품 세기
            for (int j = i; j < i + 10; j++) {
                discountMap.put(discount[j], discountMap.getOrDefault(discount[j], 0) + 1);
            }
            
            // wantMap이랑 discountMap 비교하기
            // 이번 구간은 조건 만족한다 가정
            boolean valid = true;
            // 현재 10일짜리 할인 구간이 회원이 원하는 모든 상품 조건을 만족하는지 검사하기
            for (String key : wantMap.keySet()) { // 정현이가 원하는 상품 하나씩 꺼내오기
                // 현재 10일 구간에서 나온 상품개수 가져오기, 없응면 0 반환
                // 현재 구간에서 회원이 원하는 상품 개수 가져오기, 없으면 0 반환
                // 현재 구간에서 필요한 개수보다 적으면 실패
                if (discountMap.getOrDefault(key, 0) < wantMap.getOrDefault(key, 0)) {
                    valid = false;
                    break;
                }
            }
            
            // 정답 만족된 구간이면 answer 1 증가
            if (valid) answer++;
        }
        
        return answer;
    }
}

4. 오답 / 어려웠던 점

처음에 이중for문에서 내부 for문의 범위를 잘못 잡았다. 

// 1부터 10개 물품 세기
for (int j = 0; j < i + 10; j++) {
    discountMap.put(discount[j], discountMap.getOrDefault(discount[j], 0) + 1);
}

내부 j 시작점 0 → i로 변경

// 1부터 10개 물품 세기
for (int j = i; j < i + 10; j++) {
    discountMap.put(discount[j], discountMap.getOrDefault(discount[j], 0) + 1);
}

슬라이딩 윈도우란?

이 문제에서 핵심 아이디어는 슬라이딩 윈도우를 쓰는 것이다. discount 배열을 0번째부터 끝까지 쭉 훑으면서, 길이가 10인 구간을 잘라내 검사하는 방법이다. 슬라이딩 윈도우(Sliding Window) 는 배열이나 문자열에서 연속된 구간(subarray, substring) 을 효율적으로 탐색할 때 쓰는 알고리즘 기법이다.

  • "윈도우" = 연속된 일정 구간 (예: 길이 10짜리 구간)
  • "슬라이딩" = 그 구간을 한 칸씩 옮겨가면서 검사한다는 뜻

즉, i = 0~9 구간을 본 다음, 다음에는, i = 1~10, 그 다음에는 , i = 2~11 … 이런 식으로 한 칸씩 밀어가면서 확인하는 것이다.

for문 범위 - for (int i = 0; i <= discount.length - 10; i++) 에서 조건을 <=로 쓰는 이유

마지막 윈도우도 포함시키기 위해서이다.

예를 들면 discount.length = 12, 윈도우 크기 = 10이라 해보자.

  • 가능한 시작 인덱스는 0, 1, 2 뿐이다.
    • i=0 → discount[0 ~ 9]
    • i=1 → discount[1 ~ 10]
    • i=2 → discount[2 ~ 11] ← 마지막 윈도우

만약 i < discount.length - 10 조건만 쓰면:

  • i=0, 1 까지만 돼서 마지막 구간(i=2)을 못 본다.

그래서 반드시 <=를 써야 마지막 구간까지 포함할 수 있다.

(궁금해서) keySet 출력하면?

System.out.println(wantMap.keySet());
String[] want = {"banana", "apple", "rice", "pork", "pot"};
int[] number   = {3, 2, 2, 2, 1};

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

System.out.println(wantMap.keySet());
[pot, banana, apple, rice, pork]
  • keySet()은 Set<String> 을 반환하고
  • System.out.println 하면 Set 내부 요소들을 [] 형태로 보여준다.
  • 순서는 HashMap이라 랜덤(보장되지 않음)




Back to top