## 최소 동전으로 거슬러 주기 ##
def min_coin_count(value, coin_list):
count = 0
while value != 0:
coin_list.sort(reverse=True)
for i in range(4):
count += (value//coin_list[i])
value = (value%coin_list[i])
return count
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
[프로그래머스] 체육복
- 여분 체육복을 가진 친구 먼저 제외
def solution(n, lost, reserve):
answer = n-len(lost)
lost.sort()
lost2 = []
for i in range(len(lost)):
if lost[i] in reserve:
answer += 1
reserve.remove(lost[i])
else:
lost2.append(lost[i])
for i in range(len(lost2)):
if lost2[i]-1 in reserve:
answer += 1
reserve.remove(lost2[i]-1)
elif lost2[i]+1 in reserve:
answer += 1
reserve.remove(lost2[i]+1)
return answer
[프로그래머스] 큰 수 만들기
- 두 번의 반복문을 사용하면 비효율적 + 시간초과
- "스택"을 사용하여 숫자를 쌓아가기
- k는 제거해야하는 숫자 개수
"""오답"""
def solution(number, k):
N = len(number) - k
num_lst = list(number)
while len(num_lst) != N:
i = 0
for i in range(len(num_lst)):
if int(num_lst[i]) < int(num_lst[i+1]):
num_lst.pop(i)
break
return ''.join(num_lst)
"""변경 답안"""
from collections import deque
def solution(number, k):
stack = []
for i in range(len(number)):
while stack and k>0 and int(stack[-1])<int(number[i]):
stack.pop()
k -= 1
stack.append(number[i])
if k>0:
return ''.join(stack)[:-k]
else:
return ''.join(stack)
- Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우
-Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우
""" 1부터 n까지의 합 """
def consecutive_sum(start, end):
# base case
if end == start:
return start
# 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다 (Divide)
mid = (start + end) // 2
# 각 부분 문제를 재귀적으로 풀고(Conquer), 부분 문제의 답을 서로 더한다(Combine).
return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end)
2. Tabulation
- 단순 반복문 사용
- Table 방식으로 정리
[프로그래머스] N으로 표현
- 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return
# i: 숫자 N을 몇번 사용할지 -> i별로 나올 수 있는 숫자 dp(list)에 저장
# dp[i]를 만들기 위해서는 dp[j]와 dp[i-j]의 값을 결합해야만 더 많은 경우의 수를 고려
def iter_func(N, i, dp):
for j in range(1, i):
for num1 in dp[j]:
for num2 in dp[i-j]:
if num1+num2 <= 32000:
dp[i].add(num1+num2)
if num1-num2 <= 32000:
dp[i].add(num1-num2)
if num1*num2 <= 32000:
dp[i].add(num1*num2)
if (num2!=0) and (num1//num2 <= 32000):
dp[i].add(num1//num2)
dp[i].add(int(str(N)*i))
return dp
def solution(N, number):
dp = [set() for _ in range(9)]
for i in range(1, 9):
dp = iter_func(N, i, dp)
if number in dp[i]:
return i
return -1
[프로그래머스] 정수 삼각형
- 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동하여 최댓값 구하기
def iter_func(triangle, h, max_cache):
now = max_cache[h]
next_line = triangle[h+1]
# 다음 줄에 값을 최대값으로 갱신 # 위치가 겹침
for i in range(len(now)):
max_cache[h+1][i] = max(max_cache[h+1][i], now[i] + next_line[i])
max_cache[h+1][i+1] = max(max_cache[h+1][i+1], now[i] + next_line[i+1])
return max_cache
def solution(triangle):
max_cache = {}
# 캐시 초기화
for h in range(len(triangle)):
max_cache[h] = [0] * len(triangle[h])
max_cache[0][0] = triangle[0][0]
for h in range(len(triangle)-1):
max_cache = iter_func(triangle, h, max_cache)
return max(max_cache[len(triangle)-1])
[프로그래머스] 등굣길
- 웅덩이를 피해 오른쪽과 아래쪽으로만 움직여집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return
# [x][y]: 해당좌표까지의 경로 계산
def iter_func(puddles, x, y, dp):
path = 0
if ([x-1,y] not in puddles) and ((x-1)>=0):
path += dp[x-1][y]
if ([x,y-1] not in puddles) and ((y-1)>=0):
path += dp[x][y-1]
dp[x][y] = path
return dp
def solution(m, n, puddles):
dp = [[0]*n for _ in range(m)]
dp[0][0] = 1
puddles = [[p[0] - 1, p[1] - 1] for p in puddles]
for y in range(n):
for x in range(m):
if [x,y] == [0,0]:
continue
if [x,y] in puddles:
continue
else:
dp = iter_func(puddles, x, y, dp)
return dp[m-1][n-1] % 1000000007
