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

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

프로그래머스

먼저 시간복잡도를 생각하였습니다.

제한사항

discount의 길이가 10,000인 것을 확인하였습니다.

우리가 시간복잡도를 생각할때 10^8을 염두하고 알고리즘을 구현함으로서 해당 문제의 풀이는

N, NlogN의 시간복잡도 최소 N^2은 가지않는 시간복잡도를 염두하고 문제를 풀어야 함을 이해하였습니다.

 

먼저 풀이 코드를 보고 해설해보겠습니다.

from collections import deque

def solution(want, number, discount):
    answer = 0
    basket = []
    for i in range(len(want)):
        for k in range(number[i]):
            basket.append(want[i])
    # queue를 이용해서 풀어보자
    queue = deque()
    for item in discount:
        # queue와 basket의 길이가 같으면 큐업데이트
        if len(queue) == len(basket):
            queue.popleft()
            queue.append(item)
        else:
            queue.append(item)
        # 세일 항목수가 같으면
        # sorted를 사용하여 임시적으로 정렬
        if sorted(basket) == sorted(queue):
            answer += 1
        
    return answer

 

저는 basket을 배열형태로 먼저 구현해주었습니다.

want에 [apple,pot] , number에 [3,2]가 들어온다면 

basket = [apple, apple, apple, pot, pot]이 되도록 구현하였습니다.

그리고 queue를 이용하였습니다

문제에서는 해당 basket의 항목이 모두 할인을 받는 요일부터 회원가입을 하는 것 입니다.

따라서 queue를 이용해 그 기간동안의 할인항목을 저장하고 update 하였습니다.

임시적으로 정렬 한 이유는 queue를 정렬해버리면 순서상의 제약이있고 정렬을 안하자니 비교가 안되어서 임시정렬을 활용하여 문제를 풀이하였습니다.

 

문제소감

이번 문제는 구현문제인 것 같습니다. queue를 활용하여서 어떻게하면 세일 항목을 want와 비교 할 수 있을지 찾는것이 핵심이였습니다.