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

오.. 5분 컷.

 

def solution(want, number, discount):
    answer = 0
    for i in range(len(discount) - sum(number) + 1):
        check = []
        product = discount[i:i+sum(number)]
        for w in want:
            check.append(product.count(w))
        if check == number:
            answer += 1
    return answer

 

 

그런데 효율성 측면에서 떨어지나.. 시간이 꽤 오래 소요되는 것 같다. 

 

---

 

그래서

다른 분들 풀이 체크.

 

def solution(want, number, discount):
    basket = 0
    for i in range(len(want)):
        basket += number[i] * hash(want[i])

    s = 0
    for j in range(10):
        s += hash(discount[j])
    cnt = 0
    if basket == s:
        cnt += 1

    for k in range(len(discount) - 10):
        s += -hash(discount[k]) + hash(discount[k + 10])
        if basket == s:
            cnt += 1

    return cnt

 

 

다른 분 풀이 마음대로 올리면 안되나.. 어차피 혼자 메모용이니까.. 

 

하여간 이 분 풀이대로 하면 시간소요가 1/3로 줄어든다.

 

hash함수 사용에 안 익숙한데 좀 공부해야겠다 싶었다. 

 

해당 풀이는 string값을 구분하기 위해서 해시숫자로 바꿔준 뒤,

basket에 기준 해시값 설정하고.

s를 비교 해시값으로 설정해서. 초기값 셋팅하고

for문을 돌리며 discount범위를 수정하는 식으로 풀이되었다. (s를 큐처럼 생각하는 느낌)

 

나는 해시 문제가 왜이렇게 신박하게 느껴지는 걸까.. 내 사고력이 그다지 작동하지 않는 개념이라 그런 것 같다.

 

재밌는 문제였다.