[programmers] 콜라 문제, 기능 개발, 대충 만든 자판
💡 오늘의 학습 키워드
- 콜라 문제
- 대충 만든 자판
- 기능 개발
🥉 콜라 문제
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132267
문제 설명
오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.
정답은 아무에게도 말하지 마세요.
콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다.
빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?
단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.
문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다.
상빈이가 푼 방법은 아래 그림과 같습니다.
우선 콜라 빈 병 20병을 가져가서 10병을 받습니다.
받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다.
5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다.
받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다.
이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.
문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다.
이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때,
빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다.
기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다.
상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다.
상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.
콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b,
상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다.
상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
1. 1 ≤ b < a ≤ n ≤ 1,000,000
2. 정답은 항상 int 범위를 넘지 않게 주어집니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
먼저 빈병을 주고 콜라를 받는 과정이 반복되는 것을 재귀함수로 일반화해보았습니다.
문제 해결 과정은 다음과 같습니다.
- 빈 병을 주고 받는 새로운 콜라의 개수를 저장합니다.
- 기존 빈 병을 교환하고 남은 빈 병의 개수와 새로 받은 콜라의 개수를 더하여 다음 빈 병의 개수를 갱신합니다.
- 재귀 함수를 반복하며 새로운 콜라의 개수를 저장합니다.
- 빈 병 개수가 a개보다 적을 경우 새로 받은 콜라 개수를 리턴해줍니다.
제출해보니 다음과 같이 TC 1개가 런타임 에러로 실행에 실패하였습니다.
n의 최대값 1,000,000 일 때 python 재귀 호출 깊이 문제를 해결하기 위해 아래 코드를 추가해주었습니다.
import sys
sys.setrecursionlimit(10 ** 6)
python 언어로 재귀를 사용할 때에는 python 기본 깊이 제한이 1,000 인 점을 고려해야 합니다.
이후 반복문을 사용하여 코드를 작성해보았는데, 재귀 함수를 사용한 풀이보다 간단하게 해결할 수 있었습니다.
💡 내가 해결한 방식은?
재귀 함수
import sys
sys.setrecursionlimit(10 ** 6)
def solution(a, b, n):
# a 가 n보다 클 경우 멈춘다.
if n < a:
return 0
new_cola = n//a * b
next_cola = new_cola + (n % a)
# 재귀함수로 새로 받은 콜라를 더해준다.
return new_cola + solution(a, b, next_cola)반복문
def solution_1(a, b, n):
answer = 0
# 병 a개당 콜라 b개, 빈 병 n개로 시작
while n >= a:
# 빈 병을 새로운 콜라로 바꾼다
new_cola = n//a * b
# 새로 받은 콜라와 남은 빈 병을 더하여 n을 갱신한다
n = new_cola + (n % a)
# 새로 받은 콜라를 더해준다.
answer += new_cola
return answer
🥈 대충 만든 자판
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/160586
문제 설명
휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다.
키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.
예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면
1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.
같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다.
이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며,
특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다.
또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고,
키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다.
심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.
이 휴대폰 자판을 이용해 특정 문자열을 작성할 때,
키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.
1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과
입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때,
각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아
return 하는 solution 함수를 완성해 주세요.
단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.
제한 사항
1. 1 ≤ keymap의 길이 ≤ 100
1-1. 1 ≤ keymap의 원소의 길이 ≤ 100
1-2. keymap[i]는 i + 1번 키를 눌렀을 때 순서대로 바뀌는 문자를 의미합니다.
ex) 예를 들어 keymap[0] = "ABACD" 인 경우 1번 키를 한 번 누르면 A,
두 번 누르면 B, 세 번 누르면 A 가 됩니다.
1-3. keymap의 원소의 길이는 서로 다를 수 있습니다.
1-4. keymap의 원소는 알파벳 대문자로만 이루어져 있습니다.
2. 1 ≤ targets의 길이 ≤ 100
2-1. 1 ≤ targets의 원소의 길이 ≤ 100
2-2. targets의 원소는 알파벳 대문자로만 이루어져 있습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
주요 포인트는 keymap 에 저장된 값들을 어떻게 정제하여 targets 문자열의 값들과 비교하는지 였습니다.
단순하게 작성해 나가면 targets 문자열을 keymap의 각 열과 비교해 나가면서 반복문이 누적 되어
시간 복잡도가 증가해 다른 접근법이 필요해보였습니다.
keymap의 문자열 내 문자와 최소 횟수를 Key, Value로 맵핑 하여
딕셔너리 하나에 저장하는 방법으로 구현해보았습니다. 문제 해결 과정을 정리하면 다음과 같습니다.
- 딕셔너리로 keymap 내 문자의 최소 인덱스를 저장합니다.
- 해당 딕셔너리는 keymap 내 해당 문자의 인덱스 값을 저장합니다.
- targets 문자열을 순회하며 위 딕셔너리와 각 target의 문자를 비교합니다.
- 딕셔너리에 해당 문자가 존재하지 않으면 -1을 리턴해줍니다.
- 해당 문자가 존재하면 딕셔너리에 저장된 인덱스를 더해줍니다.
딕셔너리 keymap 통합 과정에서 인덱스 값에 따라 최소 횟수가 정해지니 enumerate로 딕셔너리에
문자와 인덱스를 함께 접근하도록 구성했습니다. 딕셔너리 저장 조건은 다음과 같습니다.
- 해당 문자가 딕셔너리에 저장되어 있지 않은 경우
- 해당 문자가 이미 저장되어 있는 경우 새로 들어오는 문자의 인덱스가 더 작을 때 (최소 횟수 충족)
이렇게 새로운 keymap 배열만 잘 구현하면 이후 targets 리스트의 문자열과의 비교는 간단히 해결할 수 있습니다.
💡 내가 해결한 방식은?
def solution(keymap, targets):
answer = []
# keymap의 값을 어떻게 순회? 하나의 리스트로 합치기
# 딕셔너리로 key 값의 최소 인덱스를 저장
min_keymap_list = {}
# keymap 문자열 최소 횟수 리스트 생성
for keys in keymap:
for i, key in enumerate(keys):
# 1. key 값이 min_keymap_list 에 없는 경우
# 2. 해당 key의 인덱스 값이 저장된 key 값의 최소 인덱스보다 작을 경우
if key not in min_keymap_list or i+1 < min_keymap_list[key]:
min_keymap_list[key] = i+1
# targets 문자열 순회
for target in targets:
min_press = 0
for word in target:
# word 값이 min_keymap_list에 없을 경우
if word not in min_keymap_list:
min_press = -1
break;
# word에 해당하는 최소 횟수 값 더하기
min_press += min_keymap_list[word]
answer.append(min_press)
return answer
🥇 기능 개발
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42586
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다.
각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고,
이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와
각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때
각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
1. 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
2. 작업 진도는 100 미만의 자연수입니다.
3. 작업 속도는 100 이하의 자연수입니다.
4. 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다.
예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
문제에서 배열에 값을 추가하고 삭제하는 로직이 반복되어 queue나 deque를 사용하기로 결정했습니다.
문제 해결은 다음 순서로 해결될 수 있었습니다.
- 작업 진도 리스트가 텅 빈 상태가 될 때까지 반복합니다.
- 작업 진도 리스트의 작업들을 속도 리스트에 맞춰 하루씩 증가합니다.
- 하루 증가시킨 동안 리스트 앞쪽부터 반복문을 통해 완료일이 100일이 된 값들을 pop(0) 해서 제거해줍니다.
- 제거한 만큼 증가한 배포 기능들의 수를 append 하여 리턴해줍니다.
조건에 맞게 리스트에 값을 추가, 삭제 해주기만 해도 풀리는 문제였습니다.
이 문제는 시간복잡도 측면에서 재미있는 고민을 해볼 수 있었습니다.
list로 구현 후 pop(0)을 해주게 되면 시간 복잡도는 O(n), deque의 popleft()는 O(1) 입니다.
이론 상 시간 복잡도는 popleft( )가 더 효율적이고 전체 시간복잡도에도 큰 영향을 줍니다.
하지만 TC 결과는 정반대로 list를 사용한 풀이가 더 빠르게 나왔습니다.
이유를 고민해보니 답은 제한 사항에 있었습니다.
작업 진도와 작업 속도가 100 이하의 자연수이기 때문에 list와 deque 로 구성한 풀이 성능에
유의미한 차이가 발생하지 않은 것이었습니다.
오히려 deque는 사용할 때 발생하는 초기화, 메모리 할당 비용에서 오는 성능 저하가 반영되었다고 생각합니다.
List와 Deque 풀이 시간 복잡도 비교
- List TC 결과
- Deque TC 결과
💡 내가 해결한 방식은?
deque를 통한 구현
def solution(progresses, speeds):
answer = []
p_deque = deque(progresses)
s_deque = deque(speeds)
# 배포는 앞의 기능 완료일을 기준으로 이루어짐
while p_deque:
# 기능 속도에 맞게 각 작업 진도 하루씩 증가
for i in range(len(p_deque)):
p_deque[i] += s_deque[i]
complete_cnt = 0
while True:
# progresses 첫번째 값 기능 완료일이 100이 아니라면
if not p_deque or p_deque[0] < 100:
break
# progress, speed 첫번째 값 제거
p_deque.popleft()
s_deque.popleft()
# 기능 완료 횟수 더하기
complete_cnt += 1
if complete_cnt == 0:
continue
answer.append(complete_cnt)
return answerlist를 통한 구현
def solution(progresses, speeds):
answer = []
# 배포는 앞의 기능 완료일을 기준으로 이루어짐
while progresses:
# 기능 속도에 맞게 각 작업 진도 하루씩 증가
for i in range(len(progresses)):
progresses[i] += speeds[i]
complete_cnt = 0
while True:
# progresses 첫번째 값 기능 완료일이 100이 아니라면
if not progresses or progresses[0] < 100:
break
# progress, speed 첫번째 값 제거
progresses.pop(0)
speeds.pop(0)
# 기능 완료 횟수 더하기
complete_cnt += 1
if complete_cnt == 0:
continue
answer.append(complete_cnt)
return answer
✍️ TIL
내가 효율적이라고 생각한 접근법에 따라 문제를 풀어나가도 문제 로직의 규모나 제한 사항의 크기에 따라
일반적인 풀이라고 생각한 접근이 더 간단하고 효율적일 수 있다는 것을 알수 있었다.
첫 번째 문제에서 재귀적 접근법이 좋을 거라 생각했지만 반복문이 간결하고 가독성이 좋게 풀렸고..
세 번째 문제에서 deque를 통한 풀이가 빠르게 풀린다 생각했지만 제출하니 list가 더 빨랐다..
지금보다 문제를 조금 더 입체적으로 볼 줄 알아야 할 것 같다.
개인적으로 문제를 다각적으로 풀어보려 노력하는데, 오늘 문제들은 특히 좋은 문제들이 많았다.
아 그리고 오늘 두 번째 문제를 통해 딕셔너리 활용도 처음해보았다.
딕셔너리에서 key, value 를 활용하는 방법도 미리 공부해두자.