프로그래머스 할인 행사

 

생각이 흐르는 대로 풀었다.

 

자료구조 MAP을 이용했다.

그리고 연속되는 N개의 상품이 전부 원하는 상품의 갯수들과 딱 맞아 떨어지려면

 

1. 원하는 상품 목록에 없는 상품이 등장하면 안되고

2. 원하는 상품 갯수가 초과되면 안된다

 

두 조건을 생각해내서 반복문의 탈출 조건으로 만들었다.

 

또한 1번의 경우에는 아예 그 다음 인덱스로 건너뛰기를 함으로써 불필요한 과정을 최소화시키고 (KMP 느낌)

2번의 경우에는 하나씩 해줘야 하므로 한 칸만 건너뛴다 (Brute Force 느낌)

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;

    map<string, int> wantMap;
    int windowSize = 0;
    
    int productSize = want.size();
    int discountSize = discount.size();
        
    for(int i = 0; i < productSize; i++) {
        wantMap[want[i]] = number[i];
        windowSize += number[i];
    }
    
    
    int i, j;
    for(i = 0; i + windowSize <= discountSize; i++) {
        
        map<string, int> discountMap;

        for(j = i; j < i + windowSize; j++) {
            
            
            if(wantMap[discount[j]] == 0) { // 아예 존재하지도 않는 상품은 최대 건너뛰기
                i = j;
                break;
            }
            
            if(wantMap[discount[j]] < ++discountMap[discount[j]]) {
                // 상품이 더 많아
                break;
            }
            
        }
        
        if(j == i + windowSize)
            answer++;
        
    }
    
    
    return answer;
}

 

근데 나는 10일이라는 고정의 시간을 못보고 가변적인 날짜가 모두 적용가능하게 변수로 지정해놨었네..

 

그래서 다시 좀 다듬었다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    
    int answer = 0;

    map<string, int> wantMap;
    
    int productSize = want.size();
    int discountSize = discount.size();
        
    for(int i = 0; i < productSize; i++)
        wantMap[want[i]] = number[i];
    
    
    int i, j;
    for(i = 0; i + 10 <= discountSize; i++) {
        
        map<string, int> discountMap;
        for(j = i; j < i + 10; j++) {
            
            // 아예 존재하지도 않는 상품은 최대 건너뛰기
            if(wantMap[discount[j]] == 0) {
                i = j;
                break;
            }
            // 상품이 기대보다 더 많아
            if(wantMap[discount[j]] < ++discountMap[discount[j]]) 
                break;
        }
        if(j == i + 10)
            answer++;
    }
    return answer;
}

풀고 나니 다른 분들은 어떻게 풀었나 궁금해졌다.

 

완전 잘 푸신 분은, 10일이라는 명확한 기준이 있으니까

"먼저 10 단위로 짤라서, 11번째 상품을 추가한 뒤에, 전체 배열이 기존과 맞느냐의 작업 + 사이즈에 변수를 따로 선언하지 않음"

인데, 내 방법이 더 효율적인 것 같다.