[프로그래머스] 할인 행사 / 자바(Java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131127

프로그래머스

 

---

해설

2개의 map을 사용하여 생각보다 간단하게 해결했습니다.

1. want, number배열을 기억하여 답을 확인해줄 Map (input)
2. discount의 값을 하나씩 받으며 최근 10일간의 정보만을 가질 Map(counter)

number의 원소합은 10이므로 오직 둘이 같은 경우에만 모든 물건을 원하는 만큼 살수 있으므로 두 Map이 같다면 answer를 늘려줍니다.

2중 for문이 생기지만 전체 discount의 길이(100,000) * want의 길이(10)이므로 시간복잡도 걱정없이 사용 가능합니다.

 

---

코드

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        Map<String, Integer> input = new HashMap<>();
        Map<String, Integer> counter = new HashMap<>();
        
        for(int i=0;i<want.length;i++){
            input.put(want[i],number[i]);
        }
        
        for(int i=0;i<discount.length;i++){
            // index를 따라가며 10개의 값만 활성화하도록 지정
            counter.put(discount[i],counter.getOrDefault(discount[i],0)+1);
            if(i>=10) counter.put(discount[i-10],counter.get(discount[i-10])-1);
            
            // 모범답과 모두 같다면 answer에 하루 추가
            boolean fail = false;
            for(String cur : input.keySet()){
                if(!input.get(cur).equals(counter.get(cur))){
                    fail = true;
                    break;
                }
            }
            answer += fail ? 0 : 1;
        }
        
        return answer;
    }
}