99클럽 코테 스터디 27일차 TIL + 시뮬레이션

오늘의 문제 - 시뮬레이션

프로그래머스 - 할인 행사

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

---

내 풀이 및 접근 방식

이번에도 dictionary를 활용해야하겠다는 생각이 먼저 들었고, 시뮬레이션 유형이므로 discount를 하나씩 순차적으로 탐색하며 dictionary를 갱신해주면 해답을 구할 수 있을 것이라고 판단했다.

def solution(want, number, discount):
    answer = 0
    dic = {}
    for i, w in enumerate(want):
        if w not in dic:
            dic[w] = number[i]
        else:
            dic[w] += number[i]
            
    cnt = 0	# 날짜 수
    for idx, d in enumerate(discount):
		
        if cnt == 10:
            if discount[idx-10] in dic:
                dic[discount[idx-10]] += 1
            cnt -= 1
        
        if d in dic:
            dic[d] -= 1
            
        cnt += 1
        
        if all(value <= 0 for value in dic.values()):
            answer += 1
        # print(dic, cnt, answer, d)
        
    return answer

 

풀이

1. 사전 초기화:
   • want의 각 물품을 키로 하고, 그에 해당하는 number의 수량을 값으로 설정하여 dic을 초기화한다.
2. 할인 상품 순회:
   • 만약 cnt가 10이 되면, 10일간의 상품을 검사한 것이다. 이때 10일 중 처음 할인 행사한 상품을 제외하고 현재 상품을 반영하기 위해 10일 중 처음 할인 행사한 상품의 dic 수량을 증가시킨다. 그리고 cnt를 감소시킨다.
   • 현재 상품 d가 사전에 존재하는 경우, 그 수량 값을 감소시킨다.
   • 할인 상품을 하나씩 순회할 때마다 cnt를 증가시킨다.
   • dic의 모든 값이 0인지 all() 함수를 통해 확인한다. 만약 모든 값이 0이면 필요한 모든 물품이 원하는 수량만큼 정확히 포함된 기간임을 의미하므로 answer를 증가시킨다.
3. answer로 반환한다.

시간 복잡도

1. 사전 초기화:
   • want 리스트의 길이를 n이라고 하면, 사전을 초기화하는 데 필요한 시간은 O(n)이다.
2. 할인 상품 순회:
   • discount 리스트의 길이를 m이라고 하면, 이 리스트를 순회하는 데 걸리는 시간은 O(m)이다.
   • 각 순회에서 사전의 값을 갱신하고 모든 값이 0인지 확인하는 데 걸리는 시간은 O(n)입니다. 따라서 이 부분의 최악의 시간 복잡도는 O(m * n)이다.

전체 시간 복잡도: O(m * n)

---

다른 풀이

Counter를 이용한 풀이

from collections import Counter
def solution(want, number, discount):
    answer = 0
    dic = {}
    for i in range(len(want)):
        dic[want[i]] = number[i]

    for i in range(len(discount)-9):
        if dic == Counter(discount[i:i+10]): 
            answer += 1

    return answer

---

회고

사전의 value 값들이 모두 0인지 확인하기 위해 for문을 활용하려고 했으나, all이라는 함수가 있는 것을 발견하고 사용했다.

all(<Iterable>)

all 함수는 인자로 받은 반복 가능한 타입의 요소가 모두 참이면 참을 반환하고, 하나라도 거짓이면 거짓을 반환한다.

any(<Iterable>)

any 함수는 인자로 받은 반복 가능한 타입의 요소 중 하나라도 참이면 참을 반환하고, 모든 요소가 거짓이면 거짓을 반환한다.