프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이1]

⌛ 시간초과 (75/100 점)

def solution(want, number, discount):
    from collections import deque,Counter
    
    answer = 0

    want_n = {w:n for w,n in zip(want,number)}

    discount_queue = deque(discount)

    while len(discount_queue)>=10:

        discount_counter = dict(Counter(list(discount_queue)[:10]))

        if discount_counter == want_n:
            answer += 1


        discount_queue.popleft()

    return answer

구매자가 원하는 물품/갯수를 입력받고 날마다 1제품씩 할인하는 마트에서 연속적으로 할인된 가격에 구매할 때의 경우의 수를 구하는 문제입니다. 구매자는 항상 10개의 물품을 구매하므로 구매자가 원하는 물품/갯수의 dict와 10일 동안 할인하는 물품/갯수를 비교하여 카운트하는 식으로 구현하였습니다. 하지만 3개 테스트 케이스에서 시간초과가 나 이를 해결하고자 하였습니다.

[나의 풀이2]

def solution(want, number, discount):
    from collections import deque,Counter
    
    answer = 0

    want_n = Counter({w:n for w,n in zip(want,number)})

    discount_queue = deque(discount)

    while len(discount_queue)>=10:
        
        is_answer = True
        discount_counter = Counter(list(discount_queue)[:10])

        for k in discount_counter.keys():
            try :
                if discount_counter[k] == want_n[k]:
                    continue
                else:
                    is_answer = False
                    break
            except:
                is_answer = False
                break


        if is_answer:
            answer += 1
        discount_queue.popleft()

    return answer

'나의 풀이1'과 유사한 방식이되 dict형태이기 때문에 hash를 활용하여 구현한다면 시간을 줄일 수 있을 거라고 생각했지만 오히려 시간이 늘어난 케이스가 많았습니다. 해결하기 어려워 다른 풀이를 참고하였습니다.🐳🐳🐳

[다른사람의 풀이1]

from collections import Counter

def solution(want, number, discount):
    answer = 0
    check = {}
    for w, n in zip(want, number):
        check[w] = n
    
    for i in range(len(discount)-9):
        c = Counter(discount[i:i+10])
        if c == check:
            answer += 1

    return answer

예상밖으로 해결한 풀이 방식이었습니다. '나의 풀이1,2'와 원리는 정확히 동일하지만 경우의 수를 체크하는 범위를 len(discount)-9번으로 정의하고 discount 리스트를 인덱스로 접근하므로써 더 빠른 속도로 구현해낸 풀이입니다. 저의 풀이와 다른점은 경우의 수를 체크하는 범위를 queue구조의 최소한의 길이로 판단하고 queue.popleft()하는 점인데 이 과정자체에서 시간이 오래걸린 것을 알게 되었습니다.🦝🦝🦝

[다른사람의 풀이2]

def solution(want, number, discount):
    answer = 0
    list_all_want = []

    for i in range(len(want)):
        for j in range(number[i]):
            list_all_want.append(want[i])
    list_all_want.sort()

    for i in range(len(discount) - 9):
        list_10 = discount[i: i+10]
        list_10.sort()
        if list_all_want == list_10:
            answer += 1

    return answer

리스트만 활용하여 구현한 방식입니다. 구매해야하는 물품을 전부 나열하고 정렬하여 구매리스트(list_all_want)를 만들고 이를 할인 품목과 바로 비교하여 계산하는 풀이입니다. 직관적인 방식임에도 가장 빠른 속도로 결과를 도출하는 코드였습니다.🐦🐦🐦

감사합니다.