[연습문제] 할인 행사 - Python

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/131127

프로그래머스

 

[문제 간단 요약]

1. 고객(정현)이 원하는 제품을 연속으로 할인가로 살 수 있는 회원가입 일자를 구하는 문제

2. 회원 기간은 10일이고 해당 제품 전부를 구매할 수 있어야함

[문제 해결 방안]

1. 슬라이딩 윈도우 알고리즘을 활용해서 문제 해결

2. 회원 시작 기간 10개 범위에서 딕셔너리를 설정

3. 10개의 범위를 하나씩 이동하며 계산 

 

[문제 해결 코드 - python]

def check_subp(dic):
    for val in dic.values():
        if val > 0:
            return False
    return True

def solution(want, number, discount):
    answer = 0
    cust_product = dict()
    for i in range(len(want)):
        cust_product[want[i]] = number[i]
    for i in range(0,10):
        if discount[i] in cust_product:
            cust_product[discount[i]] -= 1
    answer += check_subp(cust_product)
    for i in range(0, len(discount)-10):
        if discount[i] in cust_product:
            cust_product[discount[i]] += 1
        if discount[i+10] in cust_product.keys():
            cust_product[discount[i+10]] -= 1
        answer += check_subp(cust_product)
    return answer

 

[다른 문제 해결 코드 - python]

from collections import Counter
def solution(want, number, discount):
    answer = 0
    dic = {}
    for i in range(len(want)):
        dic[want[i]] = number[i]

    for i in range(len(discount)-9):
        if dic == Counter(discount[i:i+10]): 
            answer += 1

    return answer

성능 및 메모리 효율 비교

	첫 번째 코드 (슬라이딩 윈도우)	두 번째 코드 (Counter 사용)
시간 복잡도	O(N)	O(NM)
공간 복잡도	O(M)	O(M)
장점	빠름, 슬라이딩 윈도우 활용	코드가 간결함
단점	check_subp(dic)에서 values() 순회 비용 존재	Counter를 매번 새로 생성하여 비효율적

[문제 해결 코드 - javascript]

function check_subp(dic) {
    for (let val of Object.values(dic)) {
        if (val > 0) {
            return false
        }
    }
    return true
}

function solution(want, number, discount) {
    var answer = 0;
    let cust_product = {}
    for (let i=0; i < want.length; i++) {
        cust_product[want[i]] = number[i]
    }
    for (let i = 0; i < 10; i++) {
        if ((discount[i] in cust_product)) {
            cust_product[discount[i]] -= 1
        }
    }
    answer += check_subp(cust_product)
    for (let i=0; i < discount.length-10; i++) {
        if (discount[i] in cust_product) {
            cust_product[discount[i]] += 1
        }
        if (discount[i+10] in cust_product) {
            cust_product[discount[i+10]] -= 1
        } 
        answer += check_subp(cust_product)
    }
    return answer;
}