[스택/큐] 프로그래머스 기능개발 - 파이썬

기능개발 파이썬 풀이

문제설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 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

1. 가장 먼저, 슬라이싱에서 인덱스 변수로 바꿔서 개발 대상인 기능과 뒤따르는 기능들의 개발 일수를 쉽게 비교하고 코드의 가독성을 높였다.
2. 2번째 for문에서 idx는 현재 개발중인 작업의 인덱스이고 i는 뒤따르는 개발 작업의 인덱스이다.
3. 만약, 뒤따르는 작업의 개발 일수가 더 오래 걸린다면 앞선 개발을 배포한다. i에서 idx를 빼면, 둘 사이의 작업의 개수가 나오고 이게 바로 한 번에 배포될 작업의 수이다!
4. 앞선 개발의 배포가 끝났다면, 다시 개발 일수 비교를 시작할 인덱스를 i로 바꿔준다.
5. 반복문에서 조건을 만족하지 못해 마지막에 남은 배포 개수는 총 작업 개수에서 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

• 문제 조건을 잘 살펴보자. 이 문제에서는 기능 배포 시점을 어떻게 판단할 지가 가장 중요했는데 프로그래머스의 다른 풀이를 참고하여 보면 내 방법이나 참고 풀이 말고도 배포 날짜 계산에 다양한 방법이 쓰인다.
• 복잡하게 푼 다음에, 테스트를 통과하지 못했다면 단순하게 바꿔보자. 오히려 단순한 방법이 정도일 수 있다.

++ 아무리 오랜만에 코테 공부를 한다해도 너무 오랜만인지 웬만한 파이썬 문법도 알고리즘도 다 잊어버렸다.. 복습 빡시게 해야지!