[JAVA/프로그래머스] 할인 행사

안녕하세요.

문제

이 문제는 XYZ마트에서 10일간의 회원 자격을 얻고, 이 기간 동안 매일 할인되는 특정 제품들을 구매하는 상황을 모델링 합니다. 목표는 원하는 제품 모두를 할인 가격으로 구매할 수 있는 최적의 10일간을 찾는 것 입니다.

 

방법

이 문제를 해결하기 위해, 해시맵을 사용하여 원하는 제품 목록과 각 제품의 수량을 따로 생성하였으며, 슬라이딩 윈도우 기법을 사용하여 10일간의 할인 제품 목록을 처리하였습니다.

 

코드

import java.util.HashMap;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        HashMap<String, Integer> productMap = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            productMap.put(want[i], number[i]);
        }

        HashMap<String, Integer> currentMap = new HashMap<>();
        for (int i = 0; i < 10; i++) {
            currentMap.put(discount[i], currentMap.getOrDefault(discount[i], 0) + 1);
        }

        for (int i = 10; i <= discount.length; i++) {
            if (currentMap.equals(productMap)) {
                answer++;
            }

            if (i < discount.length) {
                currentMap.put(discount[i], currentMap.getOrDefault(discount[i], 0) + 1);
            }
            currentMap.put(discount[i - 10], currentMap.get(discount[i - 10]) - 1);
            if (currentMap.get(discount[i - 10]) == 0) {
                currentMap.remove(discount[i - 10]);
            }
        }

        return answer;
    }
}

• 해시맵 사용 : "productMap' 해시맵은 원하는 제품과 그 수량을 저장합니다. 'currentMap' 해시맵은 현재 검토중인 10일간의 할인 제품과 그 수량을 저장합니다.
• 슬라이딩 윈도우 : 10일 간격의 윈도우를 할인 목록에 슬라이딩하여 각 10일간의 제품 조합을 검토합니다.
• 조건 검사 : 현재 윈도우가 원하는 제품 목록과 정확히 일치하는지 확인합니다.

성능분석

• 시간 복잡도: O(n), 여기서 n은 'discount' 배열의 길이 입니다. 각 할인 제품은 한 번씩만 처리됩니다.
• 공간 복잡도: O(m) , 여기서 m은 'want' 배열의 길이 입니다.

 

감사합니다.