프로그래머스 할인행사

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

프로그래머스

 

처음에는 완전탐색으로 품

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        for(int i=0; i<10; i++){
            String[] wants = want;
            int[] numbers = number;
            for(int j=i; j<i+10; i++){
                for(int k=0; k<wants.length; k++){
                    if(discount[j]==wants[k]){
                        numbers[k]--;
                    }
                }
            }
            boolean flag = true;
            for(int q : numbers){
                if(q!=0) flag=false;
            }
            if(flag) answer++;
        }
        return answer;
    }
}

시간초과가 발생하여 더 좋은 방법이 없나 생각하다 hashmap사용하기로 변경

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        HashMap<String,Integer> map = new HashMap<>();
        HashMap<String,Integer> nmap = new HashMap<>();
        for(int i=0; i<want.length; i++){
            map.put(want[i],number[i]);
        }
        
        for(int i=0; i<10; i++){
            nmap = map;
            for(int j=i; j<i+10; i++){
                nmap.put(discount[j],nmap.getOrDefault(discount[j],0)-1);
            }
            boolean flag = true;
            for(String q : nmap.keySet()){
                if(map.get(q)!=0) {flag=false;break;}
            
            }
            if(flag) answer++;
        }
        return answer;
    }
}

근데 시간초과가 발생한다 

그럼 여기서 어떻게 고쳐야하지

 

i for문의 범위가 잘못됨

jfor문의 조건이 잘못됨

nmap에 map을 집어넣는게 아니라 새로운 map을 파서 nmap과 map의 갯수를 비교해야함

import java.util.*;
class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        HashMap<String,Integer> map = new HashMap<>();
        
        for(int i=0; i<want.length; i++){
            map.put(want[i],number[i]);
        }
        
        for(int i=0; i<discount.length-10+1; i++){
        HashMap<String,Integer> nmap = new HashMap<>();
            for(int j=i; j<i+10; j++){
                nmap.put(discount[j],nmap.getOrDefault(discount[j],0)+1);
            }
            boolean flag = true;
            for(String q : nmap.keySet()){
                if(map.get(q)!=nmap.get(q)){
                    flag = false;
                    break;
                }
            
            }
            if(flag) answer++;
        }
        return answer;
    }
}