[PCCP] Lv2: 할인 행사(131127) 해설

문제

- 문제 링크: 할인 행사

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: discount 벡터의 길이

- 주어진 want 벡터에 기반하여 10일 동안 할인 상품이 원하는 제품과 일치하는지 확인하므로 시간 복잡도는 O(N)

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

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    unordered_map<string, int> wantMap; // want를 키, number를 값으로 wantMap 선언
    
    for (int i = 0; i < want.size(); ++i)
        wantMap[want[i]] = number[i];
    
    for (int i = 0; i < discount.size() - 9; ++i) {
        // i일 회원가입 시 할인받을 수 있는 품목을 키, 개수를 값으로 discount_10d 선언
        unordered_map<string, int> discount_10d;
        
        // 각 할인 품목을 키로 개수 저장
        for (int j = i; j < 10 + i; ++j)
            discount_10d[discount[j]]++;
            
        // 할인 상품의 품목 및 개수가 원하는 상품의 품목 및 개수와 일치하면 카운트 증가
        if (wantMap == discount_10d) answer++;
    }
    
    return answer;
}

solution 2) solution 1 효율성 개선

- 매번 10개의 품목 업데이트 대신 가장 오래된 정보를 제거하고 최신 정보를 추가하는 방법

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

using namespace std;

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    int answer = 0;
    unordered_map<string, int> wantMap; // want를 키, number를 값으로 wantMap 선언
    
    // want의 각 아이템을 wantMap에 할당
    for (int i = 0; i < want.size(); ++i)
        wantMap[want[i]] = number[i];
    
    unordered_map<string, int> discount_set;
    // 9일치 정보를 미리 할당
    for (int i = 0; i < 9; ++i) {
        discount_set[discount[i]]++;
    }
    
    // discount_set에 최근의 정보를 추가하고, 가장 오래된 정보를 제거하는 식으로 진행
    // 비교할 때엔 항상 10일의 정보를 가지고 있다
    for (int i = 9; i < discount.size(); ++i) {
        discount_set[discount[i]]++;
        // discount_set은 discount[i-9..i]의 정보를 가지고 있음
        if (wantMap == discount_set) answer++;
        if (--discount_set[discount[i - 9]] == 0) {
            discount_set.erase(discount[i - 9]);
        }
    }
    
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- N: discount 배열의 길이

- 주어진 want 배열에 기반하여 10일 동안 할인 상품이 원하는 제품과 일치하는지 확인하므로 O(N)

import java.util.HashMap;

public class Solution {

    public int solution(String[] want, int[] number, String[] discount) {
        // want, number배열의 값을 해시맵에 저장
        HashMap<String, Integer> wantMap = new HashMap<>();
        for (int i = 0; i < want.length; i++) {
            wantMap.put(want[i], number[i]);
        }

        int answer = 0; // 총 일수를 계산할 변수 초기화

        // 특정일 i에 회원가입 시 할인받을 수 있는 품목 체크
        for (int i = 0; i < discount.length - 9; i++) {
            // i일 회원가입 시 할인받는 제품 및 개수를 담을 해시맵
            HashMap<String, Integer> discount10d = new HashMap<>();

            // i일 회원가입 시 할인받는 제품 및 개수로 해시맵 구성
            for (int j = i; j < i + 10; j++) {
                if (wantMap.containsKey(discount[j])) {
                    discount10d.put(discount[j], discount10d.getOrDefault(discount[j], 0) + 1);
                }
            }

            // 할인하는 상품의 개수가 원하는 수량과 일치하면 정답 변수에 1 추가
            if (discount10d.equals(wantMap))
                answer++;
        }


        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: discount 리스트의 길이

- 주어진 want 리스트에 기반하여 10일 동안 할인 상품이 원하는 제품과 일치하는지 확인: O(N)

def solution(want, number, discount):
    # want 리스트를 딕셔너리로 변환
    want_dict = {}
    
    for i in range(len(want)):
        want_dict[want[i]] = number[i]
        
    answer = 0 # 총 일수를 계산할 변수 초기화
    
    # 특정일 i에 회원가입 시 할인받을 수 있는 품목 체크
    for i in range(len(discount) - 9):
        discount_10d = {} # i일 회원가입 시 할인받는 제품 및 개수를 담을 딕셔너리
        
        # i일 회원가입 시 할인받는 제품 및 개수로 딕셔너리 구성
        for j in range(i, i + 10):
            if discount[j] in want_dict:
                discount_10d[discount[j]] = discount_10d.get(discount[j], 0) + 1
                
        # 할인하는 상품의 개수가 원하는 수량과 일치하면 정답 변수에 1 추가
        if discount_10d == want_dict:
            answer += 1
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: discount 배열의 길이

- 주어진 want 배열에 기반하여 10일 동안 할인 상품이 원하는 제품과 일치하는지 확인: O(N)

function isShallowEqual(object1, object2) {
    const objKeys1 = Object.keys(object1);
    const objKeys2 = Object.keys(object2);
    
    if (objKeys1.length != objKeys2.length)
        return false;

    for (const key of objKeys1) {
        const value1 = object1[key];
        const value2 = object2[key];
        
        if (value1 !== value2) {
            return false;
        }
    }
    return true;
};

function solution(want, number,discount) {
    // want 배열을 오브젝트로 변환
    const wantObj = {};
    for (let i = 0; i < want.length; ++i) {
        wantObj[want[i]] = number[i];
    }
    
    let answer = 0; // 총 일수를 계산할 변수 초기화
    
    // 특정일 i에 회원가입 시 할인받을 수 있는 품목 체크
    for (let i = 0; i < discount.length - 9; ++i) {
        const discount10d = {}; // i일 회원가입 시 할인받는 제품 및 개수를 담을 오브젝트
        
        // i일 회원가입 시 할인받는 제품 및 개수로 오브젝트 구성
        for (let j = i; j < i + 10; ++j) {
            if (wantObj[discount[j]]) {
                // discount10d[discount[j]]가 비어있다면 0으로 기본값 설정
                discount10d[discount[j]] = (discount10d[discount[j]] || 0) + 1;
            }
        }
        
        // 할인하는 상품의 개수가 원하는 수량과 일치하면 정답 변수에 1 추가
        if (isShallowEqual(discount10d, wantObj)) {
            answer += 1;
        }
    }

    return answer;
}

solution 2)

import