[프로그래머스] 할인 행사 - 파이썬

 

프로그래머스

 

문제 접근 방법

want와 number를 통해 딕셔너리를 만들고 discount 리스트를 순회하여 number 를 -1로 만드는 방식으로 접근했다.

ex) {banana : 3} 인 경우 discount에 바나나가 있을때 {banana : 2}가 된다.

 

제출코드

def solution(want, number, discount):

    dic = {}
    for w, n in zip(want, number): ###1
        dic[w] = n
	
    ###2
    iter = len(discount) - 10 + 1
    answer = 0
    for i in range(0, iter):
        n_dic = dic.copy()
        
        ###3
        for d in discount[0+i : 10+i]:
            if d in n_dic:
                n_dic[d] -= 1
        
        ###4
        buy_all = True
        for key in n_dic.keys():
            if n_dic[key] != 0:
                buy_all = False

        if buy_all:
            answer += 1
    return answer

 

###1 : want, number를 사용해서 딕셔너리를 만든다.

###2 : 몇번 순회를 할 수 있는지 iter 변수에 담는다.

###3 : discount 목록 순회를 돌며 같은 키 값이 있으면 -1로 차감한다.

###4 : 모든 키의 값이 0이 아니면 buy_all은 False, 모든 키의 값이 0이면 True이다. True인 경우 answer +1이 된다.

 

위의 코드 또한 성공을 하였지만 딕셔너리끼리 같은지 확인하는 방법을 쓰면 시간 복잡도를 줄일 수 있었다.

아래와 같이 딕셔너리끼리 비교했을떄 같으면 True, 틀리면 False를 반환하는 점을 이용한다.

if dic1 == dict2

 

 

따라서 아래와 같이 코드를 수정했다. 시간 복잡도를 줄이고 코드 또한 단순화 할 수 있었다.

def solution(want, number, discount):
    dic = {}
    for w, n in zip(want, number):
        dic[w] = n
    iter = len(discount) - 10 + 1
    answer = 0
    for i in range(0, iter):
        dic_10d = {}
        for d in discount[0+i : 10+i]:
            if d in dic_10d:
                dic_10d[d] += 1
            else:
                dic_10d[d] = 1
        if dic == dic_10d:
            answer += 1
    return answer