카카오 서버가 불타고 티스토리도 덩달아 뻗어서 반 강제적으로 알고리즘 공부를 못한 일주일 사이에 Lv1문제가 리필되었습니다. 제논의 역설도 아니고... ㅋㅋ
아무튼 유명한 콜라문제의 속임수 없는 버전입니다. 마지막에 콜라를 한 병 더 살수있다는 꼼수가 막혔음을 유의하세요!
classSolution{
publicintsolution(int a, int b, int n){
int answer = 0;
while(n >= a){
int bottle = (n / a) * b;
n = (n % a) + bottle;
answer += bottle;
}
return answer;
}
}
슬라이딩 윈도우(혹은 투포인터), 맵 자료구조의 개념을 알면 쉽게 풀 수 있는 문제입니다.
가입한 날로부터 10일간 할인을 받을 수 있는 것을 이용해 1~10일동안 살 수 있는 품목을 카운팅합니다.
만약 2~11일 동안 살 수 있는 품목이 궁금하다면, 10일간을 전부 찾을게 아니라 카운팅한 값에서 1일의 할인상품을 빼주고, 11일의 할인상품을 더해주면 됩니다.
우리가 원하는 상품목록이 있기 때문에 그 상품들만 찾아주면 되고 카운팅과 범위 처리는 예외가 나지 않도록 적당히 잘 해주면 됩니다. (설명이 좀 그런데 정말 적당히 잘 하면 됩니다. ㅋㅋ;;)
defsolution(want, number, discount) -> int:
answer = 0
product = {}
idx = 0for w in want:
product[w] = idx
idx += 1for i inrange(10):
if discount[i] in product:
number[product[discount[i]]] -= 1for i inrange(len(discount)):
if checklist(number):
answer += 1if discount[i] in product:
number[product[discount[i]]] += 1if i + 10 < len(discount) and discount[i + 10] in product:
number[product[discount[i + 10]]] -= 1return answer
defchecklist(number) -> bool:for n in number:
if n > 0:
returnFalsereturnTrue