99클럽 코테 스터디
최근에 오늘의 문제로 백준 문제 위주로 많이 올라왔는데, 이미 다 푼 것들이어서 참여하지 않고 있었다.
오늘은 간만에 프로그래머스 문제가 올라와서 참여했는데, 두 문제 다 쉬운 편이었다.
1번 문제 하노이의 탑 : https://school.programmers.co.kr/learn/courses/30/lessons/12946
2번 문제 이모티콘 할인행사 : https://school.programmers.co.kr/learn/courses/30/lessons/150368
출처 : 프로그래머스
1번 문제 하노이의 탑
풀이 접근
기초적인 재귀 문제이다. 근데 solution 자체를 재귀로 쓰기엔 무리가 있어서, 따로 함수를 만들어서 풀었다. 함수의 변수로 n뿐만 아니라 몇번 기둥에서 몇번 기둥으로 옮기는지가 필요하기 때문이다.
코드 (Python3, 통과, 최대 13.99ms, 18.8MB)
solution_from_a_to_b는 a번 기둥에서 b번 기둥으로 n개의 원판을 옮기는 것이다.
a,b를 제외한 다른 기둥의 번호를 c라 하고, 옮길 원판이 2개 이상이라면, a->c로 n-1개의 원판을 옮기고, 맨밑에 있던 제일 큰 원판을 a->b로 옮기고, 다시 c에 옮겨둔 n-1개의 원판을 b로 옮기는 게 최선이다. 그리고 구조적으로 n에서 n-1로 요구 수가 줄었기 때문에 이 행위만 재귀해도 모든 풀이가 나온다.
c = 6 - a - b는 이럴때 써먹을만한 잡기술이다. [1,2,3]에서 a랑 b 찾아서 없애고 남은 하나 쓰는건 효율도 떨어지고 세련되지 못하다.
def solution_from_a_to_b(n,a,b):
if n == 1:
return [[a,b]]
c = 6 - a - b
return solution_from_a_to_b(n-1,a,c) + [[a,b]] + solution_from_a_to_b(n-1,c,b)
def solution(n):
return solution_from_a_to_b(n,1,3)2번 문제 이모티콘 할인행사
풀이 접근
그리디하게 푸는 방법은 아마도? 없다고 생각된다.
할인율을 높이면 기준치를 넘겨서 신규 구매자가 생길 수도 있지만, 원래 구매하려던 사람의 구매비용이 줄어서 손해일 수도 있기 때문이다. 할인율을 줄일 경우에도 구매비용을 늘려서 이득 vs 구매자가 줄어서 손해에 둘 다 걸릴 수 있으므로 어느 쪽이든 그리디는 쉽지 않다.
그러면 그냥 단순한 완전탐색 구현 문제가 된다. 시간복잡도는 대략 100 * 4^7 = 400만 정도 된다.
코드 (Python3, 통과, 최대 2406.57ms, 10.4MB)
시간복잡도가 400만쯤 되면 여기서 쓸데없는 계산을 한번 늘릴 때마다 400만번씩 연산을 더 하는게 되고, 통과시간이 쭉쭉 늘어난다.
그런 면에서 엄청 세련된 방법은 아니라고 생각되지만... 일단 여기서 연산 횟수를 더 줄이는 방법은 생각하지 못했다. 가격 비교를 더 간명하게 처리할 수 있으면 줄일 수 있을 것이다.
이모티콘이 4개면 경우의 수는 4^4 = 256가지이다. 이를 0~255의 code로 정보를 함축했다.
예를 들어, code가 124이면 4진수로 1330(4)이다. 이는 4개의 이모티콘을 각각 20%, 40%, 40%, 10% 할인했음을 의미한다. 이 방법으로 0~255까지 돌리면 모든 경우의 수를 완전탐색할 수 있다.
수정 : 1330이면 4개의 이모티콘을 10%, 40%, 40%, 20% 순(0,3,3,1)으로 한 것이다. 어차피 0000부터 3333까지 완전탐색이라 신경 안 썼는데 생각해보니 앞뒤가 반대이다.
그 밑으로는 각 유저의 구매기준에 맞는지 확인해서 맞으면 구매비용을 더해주고, 총 구매비용이 기준치 이상이면 멤버십 가입으로 적용한 것 뿐인 단순 구현이다.
def solution(users, emoticons):
answer = [0,0]
n = len(users)
m = len(emoticons)
discounted = [[] for _ in range(m)]
for i in range(m):
pdt = emoticons[i] // 10 # price divided by ten
for j in range(9, 5, -1):
discounted[i].append(pdt*j)
for code in range(4**m): # 4진수 코드, 1330이면 각 이모티콘을 20%, 40%, 40%, 10% 할인하기
membership = 0
sales = 0
price_rate = []
for i in range(m):
price_rate.append(code%4) # price_rate가 0면 10%, 1이면 20%, 2이면 30%, 3이면 40%할인
code //= 4
for ratio, price in users:
bought = 0
for i in range(m):
if price_rate[i] * 10 + 10 >= ratio:
bought += discounted[i][price_rate[i]]
if bought >= price:
membership += 1
else:
sales += bought
if membership > answer[0]:
answer[0] = membership
answer[1] = sales
elif membership == answer[0] and sales > answer[1]:
answer[1] = sales
return answer