python 코딩테스트 - 프로그래머스 할인 행사

출처 : 프로그래머스

처음 든 생각

- 먼저 want와 number를 통해서 원하는 품목과 개수를 딕셔너리를 만들고 나중에 비교해야겠다.

- discount 리스트를 한 칸씩 옮겨가면서 슬라이싱을 한다. 크기가 원하는 총 개수랑 똑같으니깐 sliding window라고 해도 되네.

- window 내에서 품목, 개수 딕셔너리를 만들고 원하는 품목 딕셔너리랑 비교하면 되겠다.

 

나의 답

def solution(want, number, discount):
    answer=0
    obj = {}
    total = 0
    for i in range(len(want)):
        if want[i] not in obj:
            total += number[i]
            obj[want[i]] = number[i]
    tmp = {}
    for i in range(len(discount)-total+1):

        sliced = discount[i:i+total]
        
        for k in range(len(sliced)):
            if sliced[k] not in tmp:
                tmp[sliced[k]] = 1
            else:
                tmp[sliced[k]] += 1
        
        key_list = list(tmp.keys())
        count = 0
        for j in key_list:
            if j in obj:
                if tmp[j] == obj[j]:
                    count +=1
                if count == len(key_list):
                    answer += 1
            else:
                 continue    

        tmp = {}
            
    
    return answer

반복문을 통해서 원하는 품목의 딕셔너리를 만들어준다.

 

그 다음 임시 딕셔너리를 만들고 반복문을 돈다. 이 때 범위는 가장 최대로 오른쪽으로 슬라이딩 된 window의 시작 인덱스까지 돌아야한다.

 

그래서 슬라이싱을 한 다음 딕셔너리로 정리하고 key의 리스트 만들어준 후 obj, tmp 딕셔너리의 값을 비교해서 같은지 확인한다. 다 맞으면 answer에 1을 추가한다. 비교한 후 tmp 딕셔너리는 다시 초기화시켜준다.

 

만약에 맞는게 없으면 answer가 추가될 일이 없어 초기값 0으로 출력될 것이기에 마지막에 리턴하는데는 지장이 없다.

---

헷갈렸던 지점은

window를 어디까지 슬라이딩 시킬지

순간적으로 까먹은 딕셔너리에서 key 값들만 불러오는 문법 -> list(dict.keys()), list(dict.values()) 절대 까먹지 말자

 

정도 였던 것 같다.

 

for 문이 많이 등장하긴 했으나 따지고 보면 O(KN)이라 시간 복잡도는 O(N)이다. 그래서 실제로 완성했을 때 시간 초과도 없이 통과할 수 있었다.