✅ Programmers - 2023 KAKAO
그렇게 찾던 빡구현 문제들..
🎈 이모티콘 할인행사
이모티콘 플러스 서비스 가입자 수를 늘리고자 하며 목표는 다음과 같다.
- 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것
- 이모티콘 판매액을 최대한 늘리는 것
행사는 다음과 같은 방식으로 진행된다.
- N명의 카카오톡 사용자들에게 이모티콘 M개를 할인하여 판매
- 이모티콘마다 할인율은 상이하고 할인율은 10%, 20%, 30%, 40% 중 하나로 설정
카카오톡 사용자들은 다음 기준을 따라 이모티콘을 사거나 서비스에 가입한다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용 합이 일정 가격 이상인 경우 서비스에 가입.
입력값으로 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어질 때 행상 목적을 최대로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 리턴하는 함수 만들기
users 배열은 [비율, 가격]의 형태, emoticons 내 원소는 이모티콘의 정가를 의미한다.
def solution(users, emoticons):
answer = [0, 0]
n, m = len(users), len(emoticons)
dc = []
rate = [10, 20, 30, 40]
# 할인율 조합하여 리스트로 생성 (emoticons 배열 길이 만큼의 조합)
def search_rate(tmp, depth):
if len(tmp) == depth:
dc.append(tmp[:])
return
else:
for r in rate:
tmp[depth] += r
search_rate(tmp, depth+1)
tmp[depth] -= r
search_rate([0]*m, 0)
# 할인율 조합으로 만든 각 할인율 별로 서비스 가입자수, 이모티콘 구매 비용 합 get 표현
for d in dc:
cnt = 0
get = 0
# 각 유저별 이모티콘 구매 금액과 기준 금액 넘는지 체크
for user in users:
money = 0
for i in range(len(d)):
# 할인율이 기준보다 높은 경우에만.
if user[0] <= d[i]:
# 유저별 이모티콘 구매 금액 계산 처리
money += emoticons[i] * (100-d[i])/100
# 각 할인율 기준 금액보다 구매 금액이 커진 경우 중단
if user[1] <= money:
break
# 기준금액보다 이모티콘 구매 금액이 큰 경우 서비스 가입 처리
if user[1] <= money:
cnt += 1
money = 0
get += money
# 서비스 가입자 수가 현재 answer에 저장된 값 이상인 경우
if cnt >= answer[0]:
# 동일한 경우 매출액 더 최대치로 갱신 처리
if cnt == answer[0]:
answer[1] = max(answer[1], get)
else:
answer[1] = get
# 값 갱신
answer[0] = cnt
return answer< 풀이 과정 >
주어진 할인율을 리스트로 만들고 emoticons 배열 길이 만큼의 다양한 할인율 조합을 미리 만드는 것이 핵심.
이후 할인율 조합으로 만든 범위에다가 서비스 가입자 수, 이모티콘 매출액, 각 유저별 이모티콘 구매 금액을 계산해 유저별 기준 금액을 넘는지 안넘는지 확인을 한 후 answer 배열을 갱신해준다.
🎈 택배 배달과 수거하기
일렬로 나열된 n개의 집에 택배를 배달하고자 한다. 배달할 물건은 모두 크기가 같은 재활용 택배에 담아 배달하며 배달을 다니며 빈 재활용 상자는 수거한다.
배달할 택배들은 모두 재활용 택배에 담겨 물류창고에 있고 i번째 집은 창고와 j만큼 떨어져 있고, i번째 집과 j번째 집은 서로 j-i만큼 떨어져 있다.트럭에는 최대 cap개의 재활용 택배를 실을 수 있다. 각 집마다 배달할 택배 수와 수거할택배 수를 알고 있을 때 트럭 하나로 모든 배달과 수거를 마치고 창고로 돌아올 수 있는 최소거리를 구하고자 한다. (각 집에 배달/수거 시 원하는 개수만큼 택배를 배달/수거 가능)
수거한 재활용 택배 상자를 물류 창고에 반드시 내려야 다음 택배 배달 가능!
입력값으로 cap (트럭에 실을 수 있는 택배 수), n(집 개수), deliveries(i번째 집에 배달할 재활용 택배 상자 수), pickups(i번째 집에서 수거할 빈 상자 수)가 주어질 때 물류창고에서 시작해 모든 배달과 수거를 마치고 창고로 다시 돌아오는 최단 거리를 구하는 문제.
def solution(cap, n, deliveries, pickups):
answer = 0
deli_cnt, pick_cnt = 0, 0
for i in range(n):
deli_cnt += deliveries[n-i-1]
pick_cnt += pickups[n-i-1]
while deli_cnt > 0 or pick_cnt > 0:
deli_cnt -= cap
pick_cnt -= cap
answer += 2*(n-i)
return answer< 풀이 과정 >
배달/수거 할 상자 수를 변수로 둔다. 최단 거리를 구하기 위해선 가장 멀리 떨어진 곳부터 배달하고, 수거를 해야 한다. 따라서 주어진 deliveries와 pickups 배열의 끝 부분부터 탐색을 진행해 주고, 각 상자 수들이 0 미만이 되는 경우 cap 만큼 빼주고 거리는 2배를 곱한 값을 더해준다.
결과적으로 answer를 리턴하는 문제
