일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- Python
- 자료구조
- 데이터사이언스
- t검정
- 우선순위큐
- 백준
- 정보보안
- 레디스
- 보안기사
- 보안
- synflooding
- FastAPI
- 카카오페이면접후기
- 카카오페이
- java
- 다이나믹프로그래밍
- 정보보안기사
- 파이썬
- lightsail
- 코딩테스트
- springboot
- 딥러닝
- 리눅스
- 분산시스템
- t-test
- 프로그래머스
- 그리디
- LangChain
- 시간초과
- linux
Archives
Techbrad
[프로그래머스] 할인 행사 - 파이썬 본문
반응형
문제 접근 방법
want와 number를 통해 딕셔너리를 만들고 discount 리스트를 순회하여 number 를 -1로 만드는 방식으로 접근했다.
ex) {banana : 3} 인 경우 discount에 바나나가 있을때 {banana : 2}가 된다.
제출코드
def solution(want, number, discount):
dic = {}
for w, n in zip(want, number): ###1
dic[w] = n
###2
iter = len(discount) - 10 + 1
answer = 0
for i in range(0, iter):
n_dic = dic.copy()
###3
for d in discount[0+i : 10+i]:
if d in n_dic:
n_dic[d] -= 1
###4
buy_all = True
for key in n_dic.keys():
if n_dic[key] != 0:
buy_all = False
if buy_all:
answer += 1
return answer
###1 : want, number를 사용해서 딕셔너리를 만든다.
###2 : 몇번 순회를 할 수 있는지 iter 변수에 담는다.
###3 : discount 목록 순회를 돌며 같은 키 값이 있으면 -1로 차감한다.
###4 : 모든 키의 값이 0이 아니면 buy_all은 False, 모든 키의 값이 0이면 True이다. True인 경우 answer +1이 된다.
위의 코드 또한 성공을 하였지만 딕셔너리끼리 같은지 확인하는 방법을 쓰면 시간 복잡도를 줄일 수 있었다.
아래와 같이 딕셔너리끼리 비교했을떄 같으면 True, 틀리면 False를 반환하는 점을 이용한다.
if dic1 == dict2
따라서 아래와 같이 코드를 수정했다. 시간 복잡도를 줄이고 코드 또한 단순화 할 수 있었다.
def solution(want, number, discount):
dic = {}
for w, n in zip(want, number):
dic[w] = n
iter = len(discount) - 10 + 1
answer = 0
for i in range(0, iter):
dic_10d = {}
for d in discount[0+i : 10+i]:
if d in dic_10d:
dic_10d[d] += 1
else:
dic_10d[d] = 1
if dic == dic_10d:
answer += 1
return answer
반응형
'Programming > 코딩테스트' 카테고리의 다른 글
코테 후기 - 시간 복잡도 (0) | 2024.04.03 |
---|---|
[백준] 1966번 프린터 큐 - 파이썬 (1) | 2024.02.18 |
[백준] 1157번 단어 공부 - 파이썬 (0) | 2024.02.02 |
[백준] 1946번 신입 사원 - 파이썬 (2) | 2023.11.14 |
[백준] 10775 공항 공항 - 파이썬 Union-find (0) | 2023.10.16 |