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

[21] 할인 행사

책 구매하기

문제 정보

• 분류: 해시
• 정답률: 34%
• 권장 시간 복잡도: O(D)
• 핵심 키워드: 슬라이딩 윈도우, 해시, 10일 할인, 빈도 비교
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/131127

문제를 읽을 때 체크할 포인트

할인 시작일을 하나씩 잡아 10일 구간이 원하는 구매 목록과 정확히 맞는지 확인하는 문제다. 매번 10칸을 새로 세기보다 윈도우를 밀면서 개수만 갱신하면 깔끔하다.

배열을 처음부터 끝까지 비교하는 쪽으로 가면 코드는 길어지고 예외도 많아진다. 이 문제는 필요한 정보를 키-값으로 압축하는 순간 풀이가 짧아진다.

풀이 흐름

1. want와 number를 묶어 목표 빈도 딕셔너리를 만든다.
2. discount의 첫 10일 구간 빈도를 잡는다.
3. 이후 하루씩 밀면서 빠지는 품목과 들어오는 품목만 갱신하고 목표와 비교한다.

구현할 때 놓치기 쉬운 부분

이 문제는 10일 구간을 매번 처음부터 다시 세면 코드도 길어지고 계산도 불필요하게 반복된다. 오늘 빠지는 품목과 새로 들어오는 품목을 같이 보면서 윈도우를 한 칸씩 미는 흐름을 유지해야 한다.

파이썬 정답 코드

from collections import Counter

def solution(want, number, discount):
  # want와 number를 묶어 목표 빈도 딕셔너리를 만든다.
  need = {w: n for w, n in zip(want, number)}
  window = Counter(discount[:10])
  answer = 0

  # discount의 첫 10일 구간 빈도를 잡는다.
  if window == need:
    answer += 1

  # 이후 하루씩 밀면서 빠지는 품목과 들어오는 품목만 갱신하고 목표와 비교한다.
  for i in range(10, len(discount)):
    left = discount[i - 10]
    window[left] -= 1
    if window[left] == 0:
      del window[left]

    window[discount[i]] += 1
    if window == need:
      answer += 1

  return answer

시간 복잡도

D는 discount의 길이이고, 윈도우 크기 10은 상수로 본다.

문자열이나 날짜 구간을 한 번 훑으면서 필요한 값만 꺼내는 구조이다. 반복문의 길이가 D에 비례하고 안쪽에 추가로 커지는 반복이 없어서 선형으로 끝난다.

따라서 시간 복잡도는 O(D)이다.