[연습 문제 / 프로그래머스] 131127번 : 할인 행사

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/131127

 

Level2 문제이다! 

물건 종류와 갯수를 따로 주고, 이를 가지고 진행해야하므로 해쉬를 사용해야한다고 생각했다. 

10개 단위로 딕셔너리를 만들어서 진행하면 시간 복잡도가 걸릴 것 같아서 그렇게 안 했는데, 그렇게 했어야 하는 문제다. 

정답으로는 처음으로 할인 받는 날을 반환하는 것이 아닌 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수이다. 

 

풀이 로직

discount 가장 마지막에서 10개의 단위가 끝나야 하므로 discount는 0인덱스 부터 len(discount) - 10 인덱스까지 탐색한다

오른쪽으로 한칸씩 이동할 때마다 temp _dict 딕셔너리를 생성해 10개만큼 진행한다

탐색한 10개의 물품과 갯수를 temp_dict에 저장한 후 이게 want_dict와 같다면 days += 1을 해준다

마지막에 days를 반환한다 

 

배운 것 

딕셔너리끼리는 == 으로 일치 여부를 확인할 수 있다 

 

- 정답 풀이 :

def solution(want, number, discount):
    answer = 0
    x, y = sum(number), len(discount)
    want_dict = {want[i] : number[i] for i in range(len(want))}
    
    days = 0
    for i in range(y - x + 1):
        temp_dict = {}
        for j in range(i, i + x):
            if discount[j] in temp.keys():
                temp_dict[discount[j]] += 1
            else:
                temp_dict[discount[j]] = 1
                
        if temp == want_dict :
            days += 1
            
    return days

 

 

- 시도해본 풀이 :

음,,, 너무 장황한 것 같다 

먼저 discount의 10개를 확인한 다음 그게 answer와 같은지 확인하고, 아니라면 오른쪽으로 하나씩 추가하고 왼쪽으로 하나씩 삭제하면서 answer와 일치하는지 확인하는 건데 적절한 풀이는 아닌 것 같다 

 

매번 해쉬맵을 만들면 시간 복잡도에 걸릴 것 같아서 기존의 해쉬맵을 유지하는 방향으로 갔는데, 매번 만들어도 괜찮은 것 같다 

def solution(want, number, discount):
    days = 0
    stuff = {}
    for i in range(10):
        if discount[i] not in stuff : 
            stuff[discount[i]] = 1
        else:
            stuff[discount[i]] += 1
            
    answer = {}
    for i in range(len(want)):
        answer[want[i]] = number[i]
        
    
    flag = True
    for i in stuff.keys():
        if i not in answer or stuff[i] != number[i]:
            flag = False
            break
      
    if flag : 
        return days + 1

    else : 
        x = 0
        count = 0
        for i in range(10, len(discount)):
            if discount[i] not in stuff:
                stuff[discount[i]] = 1
            else : 
                stuff[discount[i]] += 1
            
            stuff[discount[x]] -= 1
            days += 1
            x += 1
            #stuff와 answer이 같은지 확인 
            for i in answer.keys():
                if i in stuff and stuff[i] == answer[i]:
                    count += answer[i]
                
                          
            if count == 10:
                return days + 1
            else:
                count = 0
                
        if count != 10 :
            return 0