[Lv.2] 할인 행사(Python)

코딩테스트 연습 - 할인 행사

문제요약

일정금액 지불 → 10일간 회원

회원 대상 매일 1가지 제품 할인

할인 제품은 하루에 하나씩만

정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치한 경우 회원가입 하려고 함

정현이가 가입 가능한 날짜의 총 일수 return

없으면 return 0

입력

1 ≤ want(원하는 제품 문자열 배열), number(원하는 수량 배열) ≤ 10

10 ≤ discount 배열 길이 ≤ 10^5

1 ≤ number의 원소 ≤ 10

number의 원소 합 = 10

출력

return int

불가능하면, return 0

어떻게 풀까?

discount 범위를 생각할 때, O(NlogN) 정도까지 가능

회원가입 일수가 10일 → 슬라이딩 윈도우?

⇒ 회원가입 일수가 10일일 뿐, 1일 안에도 정현이의 want가 모두 채워질 수 있음

⇒ 투포인터로 적용해서 discount for문 한 바퀴(10^5) 돌리면서 조정해주고 그 안에서 want 길이(10)만큼 돌면서 모두 충족되었는지 검사해도 시간복잡도 충분할듯

내 코드

def check_satisfied(want_num):
    for want in want_num.keys():
        if want_num[want] > 0:
            return False
    return True

def solution(want, number, discount):
    # 데이터 전처리(want, number-> dict)
    want_num = dict()
    for i in range(len(want)):
        want_num[want[i]] = number[i]
    # answer 초기화
    answer = 0
    # discount 돌면서 투포인터 적용
    start = 0
    end = 0
    # 초기화 처리
    if discount[start] in want and want_num[discount[start]] > 0:
        want_num[discount[start]] -= 1
    while end < len(discount):
        days = end - start + 1
        # 10일 초과 -> start += 1
        if days > 10:
            if discount[start] in want:
                want_num[discount[start]] += 1
            start += 1
        # 10일 전까지 -> 검사
        elif check_satisfied(want_num):
            answer += 1
            if discount[start] in want:
                want_num[discount[start]] += 1
            start += 1
        # 그 외의 경우
        else:
            end += 1
            if end == len(discount): break
            if discount[end] in want:
                want_num[discount[end]] -= 1
    return answer