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

문제 링크

풀이

할인 품목의 배열 길이가 10만이기 때문에 재귀 등으로는 풀 수 없고, O(n)의 시간복잡도로 풀어야 한다.

항상 10일치라는 제한이 있기 때문에 discount 배열을 처음부터 끝까지 10일치씩 탐색하면서 현재 구하려는 품목의 배열 number 와 일치 여부만 확인하면 된다.

하지만 매번 10개씩 슬라이싱하는 건 연산 낭비이기 때문에 하루씩 진행될 때마다 10일 전의 품목은 제거하고, 당일 품목은 추가하는 방식으로 풀었다. 추가할 때는 stuff 딕셔너리에 품목의 이름이 키, 값은 discount_stuff의 인덱스로 주어져있다. 딕셔너리의 키 값으로 품목이 존재한다면 구하려는 품목이므로 인덱스 값을 구해서 1씩 카운트를 증가하고, 그렇지 않다면 pass

def solution(want, number, discount):
	# 키 : 원하는 품목, 값 : 인덱스
    stuff = {want[idx]: idx for idx in range(len(want))}
    answer = 0
    
    # 10일 간 할인하는 품목들에 대해 연산
    # 품목이 stuff 키 값으로 존재한다면 인덱스를 구해 discount_stuff 배열에 추가
    discount_stuff = [0] * len(want)
    for i in range(10):
        idx = stuff.get(discount[i])
        if idx != None:
            discount_stuff[idx] += 1
    
    for i in range(10, len(discount)):
    	# 원하는 품목과 할인하는 품목의 개수가 일치하는 경우
        if discount_stuff == number:
            answer += 1
        
        # 다음날 빠져야 되는 품목과 다음날 추가되는 품목이 같은 거라면
        # 다음에 이행되는 연산을 수행할 필요가 없으므로 넘어감
        if discount[i] == discount[i-10]:
            continue
            
        # 다음날 추가되어야 할 품목을 더해주고
        next_idx = stuff.get(discount[i])
        if next_idx != None:
            discount_stuff[next_idx] += 1
        
        # 10일 전의 품목은 제외하기
        pre_idx = stuff.get(discount[i-10])
        if pre_idx != None:
            discount_stuff[pre_idx] -= 1
    
    if discount_stuff == number:
        answer += 1
    return answer