프로그래머스 할인 행사 자바 풀이

문제 링크

문제 요약

want, number 배열로 정현이가 원하는 제품과 수량을 표현한다
discount 배열은 XYZ 마트가 매일 할인하는 제품 목록이다
연속된 10일 동안 할인 제품 종류와 수량이 want, number와 정확히 일치해야 회원가입할 수 있다
그런 시작일이 총 몇 번 있는지 구하는 문제다

문제 풀이

처음에는 매 시작일마다 그 날부터 10일 구간을 새 Map에 처음부터 채워서 target과 비교하면 되겠다고 생각했다.

하지만 이 방식은 구간을 한 칸씩 옮길 때마다 Map을 통째로 다시 만들어야 한다.

discount의 길이가 최대 100,000이라 가능한 시작일도 그만큼 많은데, 그때마다 10개씩 새로 세는 비용이 계속 쌓인다.

이 문제의 핵심은 하루가 지날 때 구간을 통째로 다시 셀 필요 없이, 빠지는 원소 하나와 들어오는 원소 하나만 갱신하면 된다는 점이다.

먼저 첫 10일 구간을 Map에 채워 넣는다
이후 하루씩 옮기면서 discount[i-10]은 빼고 discount[i]는 더한다
매 구간마다 window가 target(want, number)과 완전히 같은지 확인해서, 같으면 answer를 하나 늘린다

여기서 놓치기 쉬운 점은, isValid에서 target에 있는 키만 확인해도 충분하다는 것이다.

number의 원소 합이 항상 10으로 고정돼 있어서, target의 수량을 모두 만족시키면 window의 10칸이 이미 다 채워진 셈이라 다른 제품이 끼어들 자리가 없다.

최종 코드

java

import java.util.*;

class Solution {
    // target에 있는 제품 개수만 확인하면 충분하다 (want 수량 합이 항상 10이라 window 전체를 커버함)
    private boolean isValid(Map<String, Integer> target, Map<String, Integer> window) {
        for (String key : target.keySet()) {
            if (!target.get(key).equals(window.getOrDefault(key, 0))) {
                return false;
            }
        }

        return true;
    }
    
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;

        Map<String, Integer> target = new HashMap<>(); // 원하는 제품별 수량
        Map<String, Integer> window = new HashMap<>(); // 현재 10일 구간의 제품별 개수

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

        // 첫 10일 구간을 미리 채운다
        for (int i = 0; i < 10; i++) {
            window.put(discount[i], window.getOrDefault(discount[i], 0) + 1);
        }

        if (isValid(target, window)) {
            answer++;
        }

        for (int i = 10; i < discount.length; i++) {
            String remove = discount[i - 10];
            String add = discount[i];

            window.put(remove, window.get(remove) - 1);

            if (window.get(remove) == 0) {
                window.remove(remove);
            }

            window.put(add, window.getOrDefault(add, 0) + 1);

            if (isValid(target, window)) {
                answer++;
            }
        }

        return answer;
    }
}

할인 행사

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

숫자 변환하기

두 원 사이의 정수 쌍