99클럽 코테 스터디 27일차 TIL - [프로그래머스] 할인 행사 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 할인 행사 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/131127

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 원하는 제품을 나타내는 문자열 배열 want[], 원하는 제품의 수량을 나타내는 정수 배열 number[], 마트에서 할인하는 제품을 나타내는 문자열 배열 discount[] (1 ≤ want.length = number.length ≤ 10, 10 ≤ discount.length ≤ 100,000)
출력 : 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수. 단, 가능한 날이 없으면 0을 리턴

가능한 시간복잡도

O(n)

알고리즘 선택

슬라이딩 윈도우

📌 코드 설계하기

1. Map을 사용하여 want 리스트의 각 제품과 number 리스트에서 필요한 수량을 매핑한다.
2. discount 배열에서 연속된 10일간의 구간을 확인하기 위해 슬라이딩 윈도우를 사용한다.
3. 시작 인덱스를 i로 하여, i부터 i+9까지의 10일간의 제품들을 discountMap에 저장한다.
4. 현재 구간에서 필요한 모든 제품을 원하는 수량만큼 구매할 수 있는지 확인한다.
5. wantMap에 저장된 각 제품과 그 수량이 discountMap에 존재하는지, 그리고 할인된 제품(discountMap)의 수량이 원하는 수량(wantMap)보다 적은지 확인한다.
6. 모든 제품을 구매할 수 있는 경우 count를 증가시킨다.
7. count를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

getOrDefault(Object key, V defaultValue)
key: 맵에서 찾고자 하는 키
defaultValue: 지정한 키가 맵에 존재하지 않을 때 반환할 기본값

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int count = 0;

        // want와 number를 Map에 저장
        Map<String, Integer> wantMap = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }

        // 10일간의 구간을 확인하기 위해 슬라이딩 윈도우 기법을 사용
        for (int i = 0; i <= discount.length - 10; i++) {
            Map<String, Integer> discountMap = new HashMap<>();

            // 현재 10일간의 제품을 맵에 저장
            for (int j = 0; j < 10; j++) {
                String product = discount[i + j];
                discountMap.put(product, discountMap.getOrDefault(product, 0) + 1);
            }

            // 현재 구간에서 원하는 제품을 모두 구매할 수 있는지 확인
            boolean canBuyAll = true;
            for (String product : wantMap.keySet()) {
                if (discountMap.getOrDefault(product, 0) < wantMap.get(product)) {
                    canBuyAll = false;
                    break;
                }
            }

            // 만약 모두 구매할 수 있다면 카운트 증가
            if (canBuyAll) {
                count++;
            }
        }

        return count;
    }
}