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

문제

 

 

풀이 #1

import math

def solution(progresses, speeds):
    stack = []  #기술 배포 대기 스택
    res = []
    for i in range(len(progresses)) :
        # days : 기능 개발까지 걸리는 일수
        # 나눗셈의 결과가 ex. 7.3일 이렇게 나오면 8일이 걸리므로 math.ceil 사용
        days = math.ceil((100 - progresses[i]) / speeds[i])
        #배포 대기중인 max일수가 현재 비교하고 있는 기능의 개발 days보다 작으면
        if stack and max(stack) < days : 
        	#기능 개수 res에 추가 후 stack clear -> 현재 비교중인 days stack에 추가
            res.append(len(stack))
            stack.clear()
            stack.append(days)
            
            print(stack)
        else :
            stack.append(days)
      
    #모두 비교 후 배포 대기중인 기술들 배포
    if stack :
        res.append(len(stack))
        
    return res

 

 

이렇게 처음엔 디자인했고, 정답 자체는 맞았다. 하지만 계속 max(stack)을 호출하기 때문에 최악의 경우 시간복잡도가 O(n^2)가 나올 수 있다고 판단했고, 시간 복잡도를 줄일 방법을 고민해본 후에 새로운 풀이도 작성했다.

 

 

풀이 #2

 

import math

def solution(progresses, speeds):
    res = []
    count = 0
    max_day = 0  # 현재 배포 그룹의 최대 소요일

    for i in range(len(progresses)):
        days = math.ceil((100 - progresses[i]) / speeds[i])

        if count > 0 and max_day < days:
            # 새로운 배포 그룹 시작
            res.append(count)
            count = 0
            max_day = 0

        max_day = max(max_day, days)
        count += 1

    if count > 0:
        res.append(count)

    return res

len(stack)을 사용하는 것 대신에, max_day라는 변수를 선언하여 병목현상을 제거했다. 그리고 stack 리스트 사용 대신에, max_day로 최댓값만 저장하고 초기화하면 되므로 공간복잡도도 낮출 수 있었다.

 

풀이 로직

 

1.  각 기능의 완료까지 걸리는 일수(days)를 math.ceil(천장함수 : 소숫점이 존재하면 위의 수로 처리)로 하여 계산한다.

2. days가 현재 그룹의 최대 배포일(max_days)보다 크면, res에 추가 후 새로운 그룹 시작(max_day = 0)

3. days가 max_day 이하이면, 같은 그룹에 묶음(count += 1)

4. 반복 끝난 후, 남은 그룹의 count 추가

 

 

Github Link    ←

BackJoon-Programmers/프로그래머스/2/42586. 기능개발 at main · jaeheonki/BackJoon-Programmers