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

문제

- 문제 링크: 할인 행사

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#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

solution 3)

import