[Algorithm] Programmers_할인 행사

💡 Programmers Lv2. 할인 행사:

sliding window를 활용한 할인 가능 일자 확인

🌱 코드 in Java

알고리즘: Sliding window

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        Map<String, Integer> bag = new HashMap<>();
        int answer = 0;
        
        for (int i = 0; i < want.length; i++)
            bag.put(want[i], number[i]);
        for (int i = 0; i < 10; i++) {
			String obj = discount[i];
            if (bag.containsKey(obj))
                bag.put(obj, bag.get(obj) - 1);
        }
        if (Collections.max(bag.values()) <= 0)
            answer++;
        for (int i = 0, j = 10; j < discount.length; i++, j++) {
            String obj1 = discount[i], obj2 = discount[j];
            if (bag.containsKey(obj1))
                bag.put(obj1, bag.get(obj1) + 1);
            if (bag.containsKey(obj2))
                bag.put(obj2, bag.get(obj2) - 1);
            if (Collections.max(bag.values()) <= 0)
                answer++;
        }
        return answer;
   }
}

문제를 풀다보니 나는 거의 뭐 map에 미친 사람 같은데.. 이게 가장 빨리 품목의 개수를 파악할 수 있는 방법이라는 생각이 들어서 이렇게 접근하였다. 사실 완벽히 맘에 들지는 않는 코드인데, 이 이상 개선 방법이 떠오르지 않아 이렇게 풀기로 하였다.

문제의 조건에 want의 총합이 늘 10이라는 것을 늦게 알았는데, 이 부분을 처음부터 생각하고 풀었다면 조금 다른 방식이 나올 수 있었을지도 모르겠으나.. 일단은 이게 최선..!

내가 접근한 방식은 구매해야하는 개수를 새로운 맵에 담고 처음 열흘치에 대해서 먼저 검사한 후 다음날들에 대해서는 전날치와 오늘치를 가감하는 식으로 sliding window를 활용하여 처리하였다. 처음 열흘간 for문을 먼저 돌리는 것에 대해서 조금 낭비인가 싶었으나, 굳이 나눈 이유는 sliding window 방식으로 처리하는 부분에서 if (i < 10)과 같은 조건문을 넣고 싶지 않았기 때문이다. 처음에 기준을 잡고, 그 이후에는 하루씩에 대해서만 검사를 하고 싶었다.

🧠 기억하자

1. map.values()

• 맵의 모든 밸류를 collection으로 반환한다

2. Collections.max()

• 최대값을 찾아준다. map.values()가 collection을 반환하기 때문에 collection의 함수인 max를 사용할 수 있다.