해당 글은 프로그래머스의 스택/큐 파트에 해당하는 문제를 풀고 공부하는 과정에서 작성한 글입니다.
틀린 부분이 있으면 댓글로 알려주세요! 감사합니다.
프로그래머스 기능개발 - http://https://programmers.co.kr/learn/courses/30/lessons/42586
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
progresses | speeds | return |
[93, 30, 55] | [1, 30, 5] | [2, 1] |
[95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
입출력 예 설명
입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.
입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.
따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.
※ 공지 - 2020년 7월 14일 테스트케이스가 추가되었습니다.
기존 코드 - queue 개념 활용 X
처음에 문제를 풀 때는 생각하는대로 바로바로 코드를 짰습니다. 해당 문제에서 가장 중요하게 고려해야할 조건은 "앞 기능의 작업이 마무리 되어야 뒷 기능도 배포될 수 있다" 입니다. pop/push를 활용하기 보다 각 원소의 값들을 확인하는 방식으로 진행했습니다. 먼저, 100이라는 "완료"된 작업을 나타내는 작업 완료 퍼센트에서 각 기능의 진행률을 빼줘서 각 기능들의 필요 작업 진행률을 구했습니다. 그리고 가장 첫번째 기능인 맨 앞 원소를 기준으로 이후 기능들의 작업 소요 일수를 기준으로 같은 배포 시기를 가지는지를 조건문으로 확인했습니다.
from math import ceil as ceil
def solution(progresses: list, speeds: list):
"""
Rule:
각 기능들은 앞의 기능이 완성되어야 배포 가능하다.
Args:
progresses(list) - 배포되어야하는 순서대로 작업의 진도가 적힌 정수 배열
speeds(list) - 각 작업의 개발 속도가 적힌 정수 배열
Return:
answer(int) - 각 배포마다 배포되는 기능의 개수
"""
answer = []
# 남은 작업량(%) = 목표 작업량 100(%) - progresses(%)
remain = [100-i for i in progresses]
# 작업 소요 일수 = 올림(남은 작업량/작업의 개발속도)
date = [ceil(r/s) for r, s in zip(remain, speeds)]
i = 1
done = 1
state = date[0]
while True:
# 전체 progresses에 대해 다 고려하면 break
if i == len(progresses):
answer.append(done)
break
# 이전에 수행 완료되어야 하는 작업 상태 보다 적은 일수라면 완료 작업 수를 추가한다.
if date[i] <= state:
done += 1
else:
answer.append(done)
state = date[i]
done = 1
i += 1
return answer
if __name__ == '__main__':
p1 = [93, 30, 55]
p2 = [95, 90, 99, 99, 80, 99]
s1 = [1, 30, 5]
s2 = [1, 1, 1, 1, 1, 1]
print(solution(p1, s1))
print(solution(p2, s2))
실행 시간
테스트 2 같은 경우 ceil아닌 if else로 나머지가 있는지 여부에 따라서도 해줘봤지만, 3.xx 처럼 남는 수가 있으면 올리는 조건문을 통해도 진행해줘봤지만 math 모듈 썼을 때와 속도 차이가 별로 안나서 math를 쓰는 방식을 유지했습니다.
테스트 1 〉 | 통과 (0.01ms, 10.2MB) |
테스트 2 〉 | 통과 (0.04ms, 10.2MB) |
테스트 3 〉 | 통과 (0.02ms, 10.2MB) |
테스트 4 〉 | 통과 (0.01ms, 10.3MB) |
테스트 5 〉 | 통과 (0.01ms, 10.2MB) |
테스트 6 〉 | 통과 (0.01ms, 10.2MB) |
테스트 7 〉 | 통과 (0.02ms, 10.2MB) |
테스트 8 〉 | 통과 (0.01ms, 10.3MB) |
테스트 9 〉 | 통과 (0.02ms, 10.2MB) |
테스트 10 〉 | 통과 (0.02ms, 10.2MB) |
테스트 11 〉 | 통과 (0.01ms, 10.3MB) |
수정 코드 - queue 개념 활용 O
해당 문제의 주제는 "스택/큐"를 사용하는 것입니다. 그래서 해당 문제는 어떤 알고리즘에 해당하는 문제일지 생각하는 것이 필요했습니다. 일단 단순히 FIFO인지 LIFO인지로 구분했을 때 해당 문제는 뒤에 기능이 작업을 마치더라도 앞의 기능이 마무리 되지 않으면 배포가 될수가 없다는 특징을 고려했을 때 FIFO에 해당하는 문제입니다. 먼저 시작되는 기능인 맨 앞 원소가 배포(OUT)되어야 다음 기능도 배포(OUT) 될 수 있다는 점이 First In First Out의 구조인 큐를 활용할 수 있는 문제라고 생각했습니다.
그래서 기존 작성했던 코드에서 deque 모듈과 popleft를 활용해 자료구조인 큐 형태로 문제를 다시 풀었습니다. 위의 방법처럼 인덱싱하는 방식이 아니라 앞 원소를 popleft하는 함수를 활용해 문제를 풀었습니다.
이외에도 문제를 다시 풀어보니, remain_date와 같은 변수 파트에서 남은 작업량과 작업 소요 일수를 구하는 과정을 하나의 list comprehension으로 표현 가능해 한 줄짜리 코드로 수정했습니다.
기존 코드나 수정 코드 모두 while문이 기능의 개수 만큼 실행되기 때문에 O(n=기능의 개수)의 시간복잡도를 가진다고 생각됩니다.
from collections import deque
from math import ceil as ceil
def solution(progresses: list, speeds: list):
"""
Rule:
각 기능들은 앞의 기능이 완성되어야 배포 가능하다.
Args:
progresses(list) - 배포되어야하는 순서대로 작업의 진도가 적힌 정수 배열
speeds(list) - 각 작업의 개발 속도가 적힌 정수 배열
Return:
answer(int) - 각 배포마다 배포되는 기능의 개수
"""
answer = []
# 작업 소요 일수 = 올림(남은 작업량(%)/작업의 개발속도)
remain_date = deque([ceil((100-p)/s) for p, s in zip(progresses, speeds)])
# 배포되는 기능의 개수 counter
cnt = 1
# 처음 작업 시작하는 기능
start = remain_date.popleft()
while True:
# remain_date에 대해 다 고려하면 break
if len(remain_date) == 0:
answer.append(cnt)
break
# 이전에 수행 완료되어야 하는 작업 상태 보다 적은 일수가 소요되는 기능인 경우
if remain_date[0] <= start:
# 적은 일수가 소요되기 때문에 popleft로 제거
remain_date.popleft()
cnt += 1
# 이전에 수행 완료되어야 하는 작업 상태 보다 많은 일수가 소요되는 기능인 경우
else:
# 많은 일수가 소요되기 때문에 start를 업데이트
start = remain_date.popleft()
answer.append(cnt)
# 해당 기능 기준으로 배포 개수 다시 셈
cnt = 1
return answer
if __name__ == '__main__':
p1 = [93, 30, 55]
p2 = [95, 90, 99, 99, 80, 99]
s1 = [1, 30, 5]
s2 = [1, 1, 1, 1, 1, 1]
print(solution(p1, s1))
print(solution(p2, s2))
실행 시간
해당 문제는 최대로 제시되는 숫자가 100까지라서 전체적으로 런타임이 오래 걸리지는 않는 문제였습니다. 테스트 2가 인덱싱 방식이 좀더 빠른 것을 확인할 수 있었습니다.
테스트 1 〉 | 통과 (0.01ms, 10.3MB) |
테스트 2 〉 | 통과 (0.06ms, 10.3MB) |
테스트 3 〉 | 통과 (0.02ms, 10.4MB) |
테스트 4 〉 | 통과 (0.02ms, 10.1MB) |
테스트 5 〉 | 통과 (0.01ms, 10.3MB) |
테스트 6 〉 | 통과 (0.01ms, 10.1MB) |
테스트 7 〉 | 통과 (0.03ms, 10.3MB) |
테스트 8 〉 | 통과 (0.01ms, 10.3MB) |
테스트 9 〉 | 통과 (0.02ms, 10.1MB) |
테스트 10 〉 | 통과 (0.02ms, 10.3MB) |
테스트 11 〉 | 통과 (0.01ms, 10.3MB) |