Lv.2 / 할인 행사

문제

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

프로그래머스

---

 

코드( 최적화 전 )

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<string, int> um;
int len = 0;

void init(vector<string> want, vector<int> number) {
    // key = 항목, value = 원하는 수
    for(int i=0; i<want.size(); i++) {
        um[want[i]] = number[i];
    }
    
    // 전체 항목 수
    len = want.size();
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    for(int start=0; start<=discount.size() - 10; start++) {
        init(want, number); // 초기화 작업
        
        // start 지점부터 10개를 확인
        for(int i=0; i<10; i++) {            
            um[discount[start+i]]--;
            if(um[discount[start+i]] == 0) len--; // 특정 항목을 모두 샀다면 len - 1
        }
        
        // 모든 항목을 살 수 있어야만 정답
        if(len == 0) answer++;
    }
    
    return answer;
}

---

 

풀이( 최적화 전 )

 

1. unordered_map (HashMap) 에 항목마다 원하는 수를 저장해준다.
2. 날마다 할인되는 항목을 알려주는 discount 벡터의 0번부터 반복을 시작한다.
3. 특정 지점마다 10일을 확인하면서 모든 항목을 살 수 있다고 판단되면 답에 포함시킨다.

이 풀이의 경우 매 과정마다 초기화해주는 과정이 필요하고 discount 에서 한 번 확인했던 항목들도 여러번 확인하게 되기에 문제에서 요구하는 시간 내에는 풀리나 최적화의 여지가 보인다.

 

코드( 최적화 후 )

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<string, int> um;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    
    // 첫 9일의 할인 항목의 갯수 확인
    for(int i=0; i<9; i++) um[discount[i]]++;
    
    // 나머지 확인
    for(int i=9; i<discount.size(); i++) {
        bool result = true;
        um[discount[i]]++; // 해당 날짜의 할인 항목 +1
        
        for(int j=0; j<want.size(); j++) { 
            if(um[want[j]] == number[j]) continue; // 원하는 항목의 원하는 수량만큼 파냐
            
            // 만약 일치하지 않는다면 특정 항목은 원하는 수량만큼 팔지 않음
            result = false;
            break;
        }
        
        if(result) answer++; // 회원가입 가능
        um[discount[i-9]]--; // 다음 날을 위해 제일 첫 날꺼는 제외
    }
    
    return answer;
}

 

풀이( 최적화 후 )

 

기존에는 원하는 항목들을 저장하는 초기화 과정을 반복하고 discount에서 10개씩 읽으면서 -1 과정을 통해 답을 찾는다.

최적화 버전에서는 첫 9일치의 discount 항목을 저장하고 시작한다. discount 의 10일째부터 반복을 시작하면서 -1 과정을 거치는 것이 아니라 단순히 원하는 수량을 저장한 want, number 벡터와 비교하며 바로바로 결과를 낼 수 있다.

 

매번 반복되는 초기화 과정과 -1 과정을 일일이 거치면서 정답에 포함되는 날인지 확인하는 자잘한 연산이 빠지면서 최적화된 결과를 보여준다.