[프로그래머스] 기능개발

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42586

📰 문제 요약

문제 설명, 입력, 출력, 조건 등 간략하게 정리

문제 설명

1. 기능은 진도가 100%일 때 서비스에 반영할 수 있다.
2. 각 기능의 개발 속도는 모두 다르기 때문에 뒤에 있는 기능이 먼저 개발될 수 있으나, 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다.

입력

• progresses : 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열
• speeds : 각 작업의 개발 속도

출력

• 각 배포마다 몇 개의 기능이 배포되는지 return

조건

• progresses, speeds의 배열의 길이는 100개 이하
• progresses < 100, speeds ≤ 100
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정

🔓 문제 접근 방식

기본 아이디어

• 같은 인덱스를 가진 기능에 작업 속도를 더하면서 100이 되었을 때마다 pop 하면서 cnt를 증가한다.

사용 알고리즘

• FIFO(First In, First Out) 여야 하므로 큐를 이용해서 구현한다.

💻 구현 방법

1. while 문을 활용하여, progresses 속 원소가 없을 때까지 진행
2. 일괄적으로 같은 인덱스에 해당하는 기능에 작업 속도를 더하기
3. 첫 번째 기능부터 진행률이 100을 넘어갈 경우, pop, cnt값 1 증가
4. 한 번 반복문이 돌 때마다 cnt 값을 answer에 추가

1차 시도 → 시간 초과

def solution(progresses, speeds):
    answer = []
    while (len(progresses) != 0) :
        cnt = 0
        for p, s in zip(progresses, speeds) :
            p += s
        
        for p in progresses :
            if p >= 100 :
                cnt += 1
                progresses.pop(0)
            else :
                answer.append(cnt)
    return answer

시간 초과가 발생하는 주요 원인은 for 루프 내에서 progresses.pop(0)을 사용하기 때문이었다.

pop(0)은 리스트의 첫 번째 요소를 제거하므로, 리스트가 길어질수록 연산 비용이 커지기 때문인데, 리스트에서 첫 번째 요소를 제거하려면 나머지 요소를 모두 이동해야 하므로 O(n)의 시간 복잡도를 가진다.

2차 시도

pop과정의 최소화와 불필요한 for문 사용을 방지하기 위해, day 라는 변수를 활용해서 일괄적으로 더하는 과정 없이, 날짜별로 판단할 수 있는 방식을 사용하기로 결정하였다.

def solution(progresses, speeds):
    answer = []
    day = 1
    cnt = 0
    while (len(progresses) != 0) :
        if progresses[0] + speeds[0] * day >= 100 :
            progresses.pop(0)
            speeds.pop(0)
            cnt += 1            
        else :
            if cnt > 0 : 
                answer.append(cnt)
                cnt = 0
            day += 1
    return answer

마지막에 진행되는 일들에 대해서 while문이 종료되면서 카운트가 진행되지 않아, answer에 추가 되지 않는 일이 발생했다.

따라서, 모든 일들이 완료된 후, (len(progresses == 0) 이 된 상황에서 마지막으로 카운팅한 cnt 값을 answer에 추가하는 코드를 추가했다.

👍🏻 최종 제출 코드

def solution(progresses, speeds):
    answer = [] # 최종 정답
    day = 1 # 작업 일자
    cnt = 0 # 배포하는 기능의 개수
    
    while (len(progresses) != 0) : # 남은 기능이 없을 때까지
        if progresses[0] + speeds[0] * day >= 100 : # 기능이 완성되면
            progresses.pop(0) # 해당 기능 배포
            speeds.pop(0) # 해당 개발속도 없애기
            cnt += 1 # 배포하는 기능의 개수 증가
        else : # 아직 기능이 완성되지 않았다면
            if cnt > 0 : # 지금까지 배포할 수 있는 기능이 있다면
                answer.append(cnt) # 해당 배포에 배포되는 기능 수 추가
                cnt = 0 # 개수 초기화
            day += 1 # 일자 주가
    if cnt > 0 : # 모든 기능 배포가 끝났을 때 마지막으로 배포해야하는 기능들이 있다면
        answer.append(cnt) # 해당 배포에 배포되는 기능 수 추가
    return answer

📝 새로 학습한 내용

zip 을 사용하여 작업 속도 반영을 편리하게 해보고 싶었는데, pop 의 시간복잡도 때문에 실패했었다.

다른 사람의 풀이를 보니, zip을 사용한 풀이가 있었는데,

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

이 코드는 작업속도(progresses와 speeds)를 기반으로, 각 작업의 완료 날짜를 계산하고, 같은 날짜에 배포할 수 있는 작업들을 묶어 그 수를 반환하는 형식이었다.

처음 코드를 봐서는 이해가 잘 가지 않아, GPT를 통해서 다시 한 번 이해를 진행해보았는데,

• Q 초기화:
  • Q는 각 배포 그룹의 정보([완료까지 필요한 날짜, 작업 수])를 저장하는 리스트입니다.
• zip(progresses, speeds):
  • progresses와 speeds를 병렬로 순회하면서 각 작업의 진행 상황(p)과 속도(s)를 가져옵니다.
• ((p - 100) // s):
  • 각 작업이 완료되기까지 필요한 날짜를 계산합니다.
  • p - 100은 작업이 완료될 때까지 남은 진행도를 계산.
  • //는 정수 나눗셈으로 몫을 구함.
  • (...)는 나머지가 있는 경우 올림 처리를 위해 사용.
    • 예: ((93 - 100) // 1) = 7 (7일 후 완료).
  • 결과적으로 이 값은 "작업이 완료되는 데 필요한 일수"를 나타냅니다.
• if len(Q) == 0 or Q[-1][0] < -((p - 100) // s)::
  • 첫 번째 조건 len(Q) == 0:
    • Q가 비어 있는 경우, 첫 작업의 완료 날짜와 작업 수를 초기화하여 추가합니다.
  • 두 번째 조건 Q[-1][0] < -((p - 100) // s):
    • 마지막으로 저장된 배포 그룹의 완료 날짜(Q[-1][0])보다 현재 작업의 완료 날짜가 늦는 경우, 새로운 배포 그룹을 생성합니다.
  • 두 조건 중 하나라도 참이면:
    • 현재 작업의 완료 날짜와 작업 수(1)를 Q에 추가합니다.
  • Q.append([-((p - 100) // s), 1])
• else::
  • 위 조건을 만족하지 않는 경우:
    • 현재 작업의 완료 날짜가 마지막 배포 그룹의 완료 날짜보다 작거나 같으므로, 해당 배포 그룹(Q[-1])의 작업 수를 증가시킵니다:

    Q[-1][1] += 1
    

• return [q[1] for q in Q]:
  • Q에 저장된 각 배포 그룹의 작업 수(q[1])만 리스트로 추출하여 반환합니다.

---

첫 번째 작업부터 완료할 수 있는 날짜를 계산하여서 리스트에 별도로 저장한 후, 이후 작업 완료를 위해 필요한 일수가 더 큰 작업이 나올 때까지의 기능을 묶어서 반환하는 형식이었다.

확실히 각 작업의 완료 날짜를 계산한 후, 배포 가능한 작업들을 그룹으로 묶어 작업 수를 반환하므로, 시간 복잡도가 효율적인 것을 확인할 수 있었다.