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

오늘의 1솔 ♬

오늘의 문제는 프로그래머스의 Lv.2 문제 할인 행사 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

문제 요약

1. 멤버십 회원에게 하루에 한 품목 할인을 적용해주는 마트가 있다
   멤버십 등록 날부터 바로 할인을 받을 수 있다

2. 할인 품목은 하루에 한 개만 구입할 수 있다

3. 정현이는 사고 싶은 품목 10개가 있다

4. 정현이는 10일 연속 마트에 가서 3번의 품목 10개를 모두 할인가로 구입하고 싶다
   알뜰하구나!

5. 정현이의 꿈을 이룰 수 있는 멤버십 등록 날짜의 총 일수를 구하라
   
   

변수 설명

	의미	데이터 형식	길이
want	정현이가 사고 싶은 품목	문자열 배열 각 원소는 1~12자의 알파벳 소문자	1 ~ 10
number	정현이가 사고 싶은 품목 별 개수 전부 더하면 10	정수 배열	1 ~ 10 want의 길이와 동일
discount	마트에서 할인하는 제품 일별 할인 품목을 쉼표로 구분	문자열 배열 각 원소는 1~12자의 알파벳 소문자	10 ~ 100,000

풀이

처음에는 딕셔너리를 이용해서 풀었다
통과는 됐는데 문득 내가 딕셔너리라는 자료구조를 좋아해서 남발하고 있는 것 같다는 생각이 들었고 ...
지금까지 매번 통과되면 끝! ^o^ ...하고 넘어갔었는데 자료구조별 차이가 많이 나려나 궁금해서 리스트를 사용해서도 풀어보았다

Dictionary

def solution(want, number, discount):
    answer = 0
    dict_wishlist = {}

    for i in range(len(want)):
        dict_wishlist[want[i]] = number[i]

    for i in range(len(discount) - 9):
        dict_tmp = dict_wishlist.copy()
        for j in range(i, i + 10):
            if discount[j] in dict_tmp and dict_tmp[discount[j]] != 0:
                dict_tmp[discount[j]] -= 1
            else:
                break
        if sum(dict_tmp.values()) == 0:
            answer += 1

    return answer

먼저 dict_wishlist라는 이름의 dictionary를 만든다

• key: 구입하고 싶은 품목 → want[i]
• value: 해당 품목에 대해 원하는 수량 → number[i]
  ex) {"사과": 6, "바나나": 4} → 사과 6개, 바나나 4개를 사고 싶어요

discount 탐색을 시작하는 인덱스는 0부터 discount 길이보다 10 작은 수까지이다
시작 인덱스부터 10일 간의 할인 품목을 살펴봐야 하니까

탐색하며 아래의 과정을 반복한다

1. dict_tmp에 dict_wishlist를 복제
2. 시작 인덱스부터 10일간의 할인 품목 조회
3. 원하는 품목이면서 원하는만큼 구입하지 못했는가? → 더 사야 하는가?
   • Yes: 해당 품목 key의 value 1 감소
   • No: 반복문 탈출

만약 정현이의 꿈이 이루어졌다면 반복문이 끝났을 때 모든 value가 0이 된다

만약 value의 합이 0이라면 answer를 1 증가시킨다

List

def solution(want, number, discount):
    answer = 0
    list_all_want = []

    for i in range(len(want)):
        for j in range(number[i]):
            list_all_want.append(want[i])
    list_all_want.sort()

    for i in range(len(discount) - 9):
        list_10 = discount[i: i+10]
        list_10.sort()
        if list_all_want == list_10:
            answer += 1

    return answer

list_all_want라는 리스트에 want[i]를 number[i]개 저장했다 → 총 10개의 원소

조금 뒤 수행할 배열 간 비교를 편리하게 하기 위해 정렬을 수행한다

discount 탐색을 시작하는 인덱스는 앞의 방식과 동일하다
0부터 discount 길이보다 10 작은 수까지 !

list_10은 discount를 시작 인덱스부터 10의 길이로 자른 리스트다

list_10에도 정렬을 수행해준 다음 list_all_want와 같은지 비교한다

만약 같다면 answer를 1 증가시킨다

결과 비교

Dictionary

List

10번 12번 제외하고는 리스트를 사용한 방식이 더 빨랐다

새로 배운 내용

• 딕셔너리를 복사할 때는

  new_dict = old_dict

  위의 방식처럼 쓰면 안된다 !
  이렇게 되면 변수 이름은 두 개지만 객체는 여전히 하나다

  new_dict = old_dict.copy()

  요렇게 해줘야 새로운 객체가 하나 복제된다
  
  

• 파이썬에서 리스트와 딕셔너리를 잘 정리해두신 블로그를 찾았다 !
  사용법부터 각 연산 별 시간 복잡도까지 ...
  이젠 ... 답만 맞았다고 넘어가면 안되니까 ... 시간 복잡도도 신경써야 하니까 ...
  울면안돼
  
  

마무리

딕셔너리 남용을 멈추자

왤케 좋아하는 건데 ?!
딕셔너리가 나쁜 자료구조라는 게 아니라 ... 이유는 모르겠지만 딕셔너리를 좋아해서 자주 써왔다

However

좋은 걸 어떡해

Nevertheless

다른 자료구조에도 관심을 가지고 다양한 방법을 이용해봐야겠다

그래 앞으로도 열심히 해보자꾸나