프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
프로그래머스 - 2023 KAKAO BLIND RECRUITMENT 이모티콘 할인행사
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 - 하노이의 탑
def solution(n):
answer = []
def hanoi(n, from_, to_, via_) :
if n == 1 :
answer.append([from_, to_])
else :
hanoi(n-1, from_, via_, to_)
# hanoi(1, from_, to_, via_)
answer.append([from_, to_])
hanoi(n-1, via_, to_, from_)
hanoi(n, 1, 3, 2)
return answer하노이의 탑
파일:external/437a6637b1f6834a74146f6e51b7360fa64116c23c3c0c7fd546
namu.wiki
def hanoi(number_of_disks_to_move, from_, to_, via_):
if number_of_disks_to_move == 1:
print(from_, "->", to_)
else:
hanoi(number_of_disks_to_move-1, from_, via_, to_)
print(from_, "->", to_)
hanoi(number_of_disks_to_move-1, via_, to_, from_)이 규칙들을 이용하여 64개의 원반을 다른 막대로 전부 옮기는 것은 간단해 보이지만 '작은 원반 위에 큰 원반을 올릴 수 없다' 는 규칙은 의외로 크게 작용하는데, 이를 지키면서 n개의 원반을 한쪽 기둥에서 다른 쪽으로 옮기는 데 걸리는 최소 횟수가 2^𝑛 번이기 때문이다.
𝑛+1번째 원반을 목표로 하는 비어있는 한 기둥으로 옮기려면, 우선 그 위의 1번부터 𝑛번째까지의 원반을 목표로 하는 기둥 이외의 비어있는 기둥으로 옮겨야만 한다. 이 사실을 이용해서 다음과 같이 1번부터 𝑛+1번째까지의 원반을 목표로 하는 기둥으로 옮기는 데 요구되는 원반이동 횟수를 계산할 수 있다.
1부터 𝑛번째까지의 원반을 빈 한 기둥으로 옮기는 데 필요한 최소 횟수를 𝑎𝑛라고 하자. 1번부터 (𝑛+1)번째까지의 원반을 목표로 하는 빈 기둥으로 옮기려면 (즉 𝑎𝑛+1을 구하려면) 𝑛번째까지의 원반을 목표로 하지 않는, 빈 다른 기둥으로 옮기고 (즉 𝑎𝑛 횟수만큼 옮기고) (𝑛+1)번째 원반을 목표로 하는 빈 기둥으로 옮긴 후 (즉 1을 더한 후) 𝑛번째까지의 원반을 목표 기둥에 꽂혀 있는 (𝑛+1)번째 원반 위로 옮기면 (즉 𝑎𝑛를 다시 더하면) 된다.
따라서 𝑎1=1, 𝑎𝑛+1=2𝑎𝑛+1이고 이 점화식 (Recursive relation)에 의한 수열 𝑎𝑛의 일반항을 구해보면 𝑎𝑛=2^𝑛 − 1 나온다.
n = 3 이라면, [[1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]]. 이 때 위에서부터 홀수번째의 원반이 왼쪽으로 이동(시프트, 더 이상 왼쪽에 막대가 없다면 맨 오른쪽으로 이동)하면 짝수번째는 오른쪽으로 이동(마찬가지로 오른쪽 끝에서 오른쪽으로 가야할 경우 왼쪽 끝으로 이동)하면 실수 없이 최소한으로만 움직일 수 있다. 이때 맨 위의 원반이 왼쪽과 오른쪽 가운데 어느 쪽으로 시프트하느냐에 따라 탑이 어느 막대로 움직이는가가 달라진다.
위의 포맷을 응용하면 쉽게 문제를 해결할 수 있다.
풀이 - 이모티콘 할인행사
from itertools import product
def solution(users, emoticons):
answer = []
# 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10, 20, 30, 40 % 중 하나로 설정됩니다.
discounts = list(product([10, 20, 30, 40], repeat = len(emoticons)))
# [(10, 10), (10, 20), (10, 30), (10, 40),
# (20, 10), (20, 20), (20, 30), (20, 40),
# (30, 10), (30, 20), (30, 30), (30, 40),
# (40, 10), (40, 20), (40, 30), (40, 40)]
for discount in discounts :
local_subscriber = 0 # 이모티콘 플러스 서비스 가입자 수
local_sell = 0 # 이모티콘 구입의 총합
for user in users :
local_user_subscriber = False # 이모티콘 플러스 서비스 가입 여부
local_user_sell = 0 # 구매한 이모티콘의 가격
user_dis, user_sell_limit = user # 할인율 이하이면 이모티콘을 구힙하는 할인율, 구입가능한 최대 이모티콘 가격의 합
# 이모티콘의 할인율이 원하는 할인율의 이하라면, 할인된 가격으로 이모티콘을 구매하고 구매한 가격을 local_user_sell에 저장
# 이모티콘을 구매한 가격의 합이 user_sell_limit의 이상이면, 해당 user는 이모티콘을 구매하지 않고, 이모티콘 플러스 서비스에 가입.
# 이모티콘 플러스 서비스에 가입하면, 더 이상 이모티콘을 구매하지 않기 때문에, break로 루프를 나오게 된다.
for idx in range(len(emoticons)) :
emo_dis, emo_price = discount[idx], emoticons[idx]
if user_dis <= emo_dis :
local_user_sell += (emo_price * (100 - emo_dis) // 100)
if local_user_sell >= user_sell_limit :
local_user_subscriber = True
break
# 이모티콘 플러스 서비스에 가입했다면, local_subscriber += 1
# 아니라면, 구매한 이모티콘의 가격의 합을 local_sell에 더해준다.
if local_user_subscriber :
local_subscriber += 1
else :
local_sell += local_user_sell
# 리스트 answer에 이모티콘 플러스 가입자 수와 이모티콘 판매 가격의 합을 append로 넣어준다.
# 첫 루프라면 answer에 1개의 원소만 들어있기 때문에, sort의 의미가 없지만, 2번째 부터는 큰 값이 앞으로 오게 된다.
answer.append([local_subscriber, local_sell])
answer.sort(reverse=True)
answer = [answer[0]]
return answer[0]
# return max(answer)return max(answer) 가 조금 더 오래 걸리고, answer 배열의 길이가 계속 길어지는 점 때문에 그런 부분에서 메모리적이나 시간적으로 오래걸리는 것 같다.
answer[0] 으로 계속 초기화 되는 부분은 시간면에서는 큰 차이 없는거 같은데 메모리 사용면에서 크게 차이가 나는거 같아 결국 시간이 덜 걸리게 되는것 같다. 자세한건 모르겠지만...
product 의 사용법이나 풀이를 풀어나가는데 있어 영 감을 못잡아서 다른 분의 풀이를 참고하였다. 더 공부해야 할 문제일 듯 하다