기능개발_알고리즘(스택/큐)

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

프로그래머스

 

[문제 설명]

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

[나의 풀이]

import math

def solution(progresses, speeds):
    # 각 작업에 남은 작업 일수 계산
    days = [math.ceil((100 - progresses[i]) / speeds[i]) for i in range(len(progresses))]
    
    answer = []
    current_day = days[0]  # 첫 번째 작업의 남은 일수를 기준으로 설정
    n = 1  # 첫 번째 작업 포함
    
    for k in range(1, len(days)):
        if days[k] <= current_day:  # 현재 작업이 이전 배포일보다 빠르면 같이 배포
            n += 1
        else:  # 새 배포 기준일 설정
            answer.append(n)
            current_day = days[k]
            n = 1
    
    # 마지막 남은 작업 수 추가
    answer.append(n)
    
    return answer

 

[다른 풀이]

1)

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]

☑️-((p - 100) // s)의 의미

처음부터 100 - p로 계산하지 않고 p - 100로 계산 한 후에 나중에 -로 부호전환을 한 이유는 파이썬의 정수 나눗셈의 특징 때문이다. 파이썬에서 //연산은 소수점을 버리고 가장 가까운 작은 정수를 반환한다. 

 

예를 들어

7 // 3 = 2
-7 // 3 = -3 (소수점을 버리고 더 작은 방향으로 가기 때문)

 

이 문제에서 원하는 것은 '남은 소수점이 있다면 무조건 올림해서 날짜를 계산 하는 것'이기 때문에 음수로 바꾼 다음 정수 나눗셈을 하면 올림과 동일한 효과를 얻을 수 있다. 

 

2)

def solution(progresses, speeds): 
    answer = []
    time = 0  # 시간 경과를 나타내는 변수
    count = 0  # 배포할 기능의 개수를 세는 변수
    
    while len(progresses) > 0:  # 모든 작업이 완료될 때까지 반복
        if (progresses[0] + time * speeds[0]) >= 100:  
            # 첫 번째 작업이 완료되었으면 배포할 준비를 함
            progresses.pop(0)  # 완료된 작업을 제거
            speeds.pop(0)  # 해당 작업의 속도 정보도 제거
            count += 1  # 배포할 기능의 개수 증가
        else:
            if count > 0:
                answer.append(count)  # 배포 가능한 기능을 저장
                count = 0  # 배포 후 다시 초기화
            time += 1  # 하루가 지나감
    
    answer.append(count)  # 마지막으로 남은 배포 기능 수 추가
    return answer

 

3)

from math import ceil

def solution(progresses, speeds):
	# 남은 작업 일수 계산
    daysLeft = list(map(lambda x: (ceil((100 - progresses[x]) / speeds[x])), range(len(progresses))))
    # 배포 그룹 초기화
    count = 1
    retList = []
	
    # 배포 그룹을 묶는 반복문
    for i in range(len(daysLeft)):
        try:
            if daysLeft[i] < daysLeft[i + 1]:
                retList.append(count)
                count = 1
            else:
                daysLeft[i + 1] = daysLeft[i]
                count += 1
        except IndexError:
            retList.append(count)

    return retList

 

(반복문의 동작과정)

 

4)

import math

def solution(progresses, speeds):
    answer = []
    rest = []
    temp = []

    size = len(progresses)

    for i in progresses:
        rest.append(100 - i)

    for i in range(size):
        temp.append(math.ceil(rest[i] / speeds[i]))

    cnt = 0
    p = temp[0]
    for i in range(len(temp)):
        if p < temp[i]:
            answer.append(cnt)
            p = temp[i]
            cnt = 0
        cnt += 1
    answer.append(cnt)


    return answer