[프로그래머스] Lv2 할인 행사

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/131127

프로그래머스

 

 

📝  풀이

이 문제는 Dictionary와 Set을 활용해서 풀었다. 또한 Sliding window 개념을 이용해 window의 크기를 10으로 지정하여 새로 들어오는 원소와 나가는 원소에 주목하여 풀었다.

먼저 사야하는 과일을 dictionary에 저장했다. 또한 나중에 반복문을 이용해 원하는 품목들을 전부 샀는지 확인하기위해 Set도 구했다. Dictionary를 이용해 반복문 돌리면서 확인할 수도 있지만 Set을 이용하면 시간복잡도를 작게 구현할 수 있다.

wantList = dict()
for i in range(len(want)):
	wantList[want[i]] = number[i]
wantSet = set(wantList)

우선 10일동안 품목들을 산다고 가정했을때 남은 품목과 개수를 저장하는 Dictionary와 Set도 갱신해준다.

for i in range(10):
    if discount[i] in wantList.keys():
        wantList[discount[i]] -= 1 
    if wantList[discount[i]] == 0:
        wantSet.remove(discount[i]) // 원하는 품목을 다샀으면 Set에서 제거해준다.
if len(wantSet) == 0: // 원하는 품목을 전부 산 경우
    ans+=1

Sliding Window를 이용해 각각 반영해준다.

for j in range(10, len(discount)):
    if discount[j] in wantList.keys(): // 사야하는 품목인 경우
        wantList[discount[j]] -= 1
        if wantList[discount[j]] == 0: // 다 샀으면 Set에서 제거
            wantSet.remove(discount[j])
        
    if discount[j-10] in wantList.keys(): // 10일 지나서 포기해야하는 품목
        wantList[discount[j-10]] += 1
        if wantList[discount[j-10]] == 1: // 다시 Set에 추가
            wantSet.add(discount[j-10])
        
    if len(wantSet) == 0: // 다샀으면
        ans+=1

🖥 최종 코드

def solution(want, number, discount):
    ans = 0
    wantList = dict()
    
    for i in range(len(want)):
        wantList[want[i]] = number[i]
    wantSet = set(wantList)
        
    for i in range(10):
        if discount[i] in wantList.keys():
            wantList[discount[i]] -= 1
            if wantList[discount[i]] == 0:
                wantSet.remove(discount[i])
    if len(wantSet) == 0:
        ans+=1        
        
    for j in range(10, len(discount)):
        if discount[j] in wantList.keys():
            wantList[discount[j]] -= 1
            if wantList[discount[j]] == 0:
                wantSet.remove(discount[j])
        
        if discount[j-10] in wantList.keys():
            wantList[discount[j-10]] += 1
            if wantList[discount[j-10]] == 1:
                wantSet.add(discount[j-10])
        
        if len(wantSet) == 0:
            ans+=1 
                
    return ans