기능개발 파이썬 풀이
문제설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. - 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
접근 방법
문제를 읽고나서, 원하는 answer 배열을 얻기 위해선 가장먼저 두 가지 문제를 해결해야 한다 생각했다.
1. 기능 개발 배포까지 걸리는 일수를 계산해야 한다.
2. 맨 앞 원소부터 기능 개발 일수를 누적해 비교하고 출력해야 한다.
위와 같이 생각하고나서 문제 풀이를 진행했다.
1차 작성 코드
def solution(progresses, speeds):
answer = []
days = []
tmp = 1
for i in range(len(progresses)):
days.append(( - 100 + progresses[i])//speeds[i] * -1)
for i in range(len(days)- 1) :
print(days[i:i+1], days[i+1:i+2])
if days[i:i+1] < days[i+1:i+2] :
answer.append(tmp)
tmp = 1
else:
tmp += 1
# 가장 마지막 작업은 그냥 append
answer.append(tmp)
return answer
# i번째 작업보다 i+1번째 작업의 개발시간이 크다면 선행한 작업을 바로 배포한다.
# 만약 i+1번째 작업의 개발시간이 적다면 선행 배포시 함께 배포한다.처음 시도한 코드는 다음과 같이 돌아가도록 생각하며 작성했다.
1. days 배열을 만들어서, 각 작업의 개발 시간을 기록한다.
2. 만들어진 days에서 아이템을 두개씩 뽑아, 더 큰 개발시간이 필요한 작업이 있다면, 선행 작업을 먼저 배포한다.
3. 지금 작업이 뒷 작업보다 더 큰 개발시간이 필요하다면, 뒤따르는 기능도 한 번에 배포한다.
1차 작성 코드의 문제점
- 1차로 작성하면서 내가 간과했던 점은, 현재 작업과 바로 뒤따르는 작업의 개발 시간만을 비교하고 있었다는 점이다.
- 뒤에 더 큰 개발시간이 소요되는 작업들이 나타날 때까지 탐색해야 했기 때문에 테스트 케이스 실패! 1, 8, 11번 테스트 케이스만 통과하고 나머지를 통과하지 못하는 코드였다!
- 하지만 반복문을 중첩하고 싶진 않아 배열의 인덱싱과 추가 아이디어를 탐색했다.
1차 코드 수정하기
def solution(progresses, speeds):
n = len(progresses)
answer = []
days = []
tmp = 1 # 기능 개발은 무조건 1개는 배포
for i in range(n):
days.append(( - 100 + progresses[i])//speeds[i] * -1)
# 인덱스로 조작
idx = 0
for i in range(1,n):
if days[i] > days[idx]:
answer.append(i - idx)
idx = i
# 가장 마지막 작업은 그냥 append
answer.append(n-idx)
return answer- 가장 먼저, 슬라이싱에서 인덱스 변수로 바꿔서 개발 대상인 기능과 뒤따르는 기능들의 개발 일수를 쉽게 비교하고 코드의 가독성을 높였다.
- 2번째 for문에서 idx는 현재 개발중인 작업의 인덱스이고 i는 뒤따르는 개발 작업의 인덱스이다.
- 만약, 뒤따르는 작업의 개발 일수가 더 오래 걸린다면 앞선 개발을 배포한다. i에서 idx를 빼면, 둘 사이의 작업의 개수가 나오고 이게 바로 한 번에 배포될 작업의 수이다!
- 앞선 개발의 배포가 끝났다면, 다시 개발 일수 비교를 시작할 인덱스를 i로 바꿔준다.
- 반복문에서 조건을 만족하지 못해 마지막에 남은 배포 개수는 총 작업 개수에서 idx를 빼주면 배포 개수를 구할 수 있다.
다른 풀이로 로직 갈아 엎기
추가적으로 다른 아이디어를 찾아보았다. 구글링에서 높은 순위로 나온 블로그의 풀이를 참고하여 보니, progresses와 speeds를 큐로 써서, progresses의 원소를 돌릴 때, 각각의 원소에 speeds를 더해가면서 맨 앞 원소가 100을 넘었을 때, 100이상의 원소들을 한 번에 배포한다.
다른 풀이 코드
def solution(progresses, speeds):
n = len(progresses)
answer = []
while progresses:
cnt = 0
# 가장 먼저 개발하고 있는 기능을 다 개발하자
while progresses[0] < 100:
progresses = [p + s for p, s in zip(progresses, speeds)]
# 각 기능의 개발 척도가 100을 넘었는지 확인
for i in progresses:
if i >= 100:
cnt += 1
else:
break
# 기능 배포 시점. 뒤따르는 개발 진행 상황을 새로 카피한다.
progresses = progresses[cnt:]
speeds = speeds[cnt:]
answer.append(cnt)
return answer
첫 주석 라인에서 볼 수 있듯, zip 연산을 통해 가장 먼저 개발하고 있는 progresses[0]이 100이 넘을 때까지 전체 개발을 진핼한다.
두번째 주석에선 첫번째 기능이 배포될 때 progresses 배열내에 배포할 수 있는 다른 기능이 있는지 확인한다. 없다면 break하고, 다음 기능부터 개발 상황을 다시 확인하기 시작한다.
TIL
- 문제 조건을 잘 살펴보자. 이 문제에서는 기능 배포 시점을 어떻게 판단할 지가 가장 중요했는데 프로그래머스의 다른 풀이를 참고하여 보면 내 방법이나 참고 풀이 말고도 배포 날짜 계산에 다양한 방법이 쓰인다.
- 복잡하게 푼 다음에, 테스트를 통과하지 못했다면 단순하게 바꿔보자. 오히려 단순한 방법이 정도일 수 있다.
++ 아무리 오랜만에 코테 공부를 한다해도 너무 오랜만인지 웬만한 파이썬 문법도 알고리즘도 다 잊어버렸다.. 복습 빡시게 해야지!
