[Programmers] Lv2. 할인 행사

https://school.programmers.co.kr/learn/courses/30/lessons/131127?language=java

프로그래머스

문제를 읽고 든 생각은 그냥 문제가 제시한대로 따라가면 풀면 될 것 같은데? 라는 생각이 들었다.

 

첫 번째 풀이

단순하게 discount 배열의 0번째부터 discount.length - 10까지 반복문을 돌면서 10개씩 자르며 원하는 수량을 다 채웠는지 체크한다.

import java.util.*;

class Solution {
    
    private boolean canRegister(String[] want, int[] number, String[] d) {
        Map<String, Integer> wantMap = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }
        
        for (int i = 0; i < d.length; i++) {
            if (wantMap.containsKey(d[i])) {
                wantMap.put(d[i], wantMap.get(d[i]) - 1);
            }
        }
        
        for (String product : wantMap.keySet()) {
            if (wantMap.get(product) >= 1) {
                return false;
            }
        }
        
        return true;
    }
    
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        for (int i = 0; i < discount.length - 9; i++) {
            if (canRegister(want, number, Arrays.copyOfRange(discount, i, i + 10))) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

문제를 풀고나서 시간복잡도를 생각해보니 너무 오래걸리는 것 같다는 생각이 들어 잘푼 풀이를 찾아보았다.

아니나 다를까, sliding window 기법을 사용하면 훨씬 빠르게 풀 수 있었다.

 

나은 풀이

import java.util.*;
import java.util.stream.*;

class Solution {
    
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        int total = Arrays.stream(number).sum();
        Deque<String> days = new LinkedList<>(Arrays.asList(discount).subList(0, total));
        
        for (int i = total; i <= discount.length; i++) {
            boolean pass = IntStream.range(0, want.length).noneMatch(j -> Collections.frequency(days, want[j]) != number[j]);
            
            if (pass) {
                answer++;
            }
            
            if (i < discount.length) {
                days.pollFirst();
                days.addLast(discount[i]);
            }
        }
        
        return answer;
    }
}

- deque를 통해 sliding window를 구현하였다.

- want배열을 돌리면서 현재 deque에 들어있는 discount의 서브 배열과 매치되는지 확인한다.

- 서브 배열을 다시 짤 필요없이 deque에 가장 앞 value를 제거하고 그 다음 부분을 맨 뒤에 추가하면 된다.

 

몇 개는 더 느려지고 몇 개는 더 빨라졌지만 전체적으로 빨라진듯..?