[스택/큐] 프로그래머스 level 2 기능개발 (Python 파이썬)

💡문제 링크

프로그래머스

💡문제 분석 요약

기능 개발은 1) 시작 2) 개발 3) 배포 순서대로 진행된다.

개발 진행상황은 1~100단계까지 있으며, 100이 되어야 개발이 완료된 것이다. 즉, 100이 되어야 배포가 가능하다.

progresses 배열에는 현재까지 개발 진행상황이 배포 순서대로 나열되어 있다.

예를 들어 progresses = [93, 30, 55]이면 세 개의 기능이 현재 93, 30, 55만큼 개발 진행되었다는 의미이다.speeds 배열에는 각 기능의 개발속도가 나열되어 있다. 개발속도가 n이면 하루에 n만큼 개발된다.예를 들어 speeds = [1, 30, 5]이면 세 개의 기능이 하루에 1, 30, 5만큼 개발된다는 의미이다.뒤의 기능이 먼저 개발 완료되었다고 하더라도(100이 되었더라도), 앞의 기능이 아직 덜 개발되었으면 배포할 수 없다.

각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 작성하는 문제.

💡알고리즘 설계

1. progresses의 i번째 원소를 p, speeds의 i번째 원소를 s라고 할 때, i번째 기능이 완성되기까지 소요되는 일수를 days 배열 i번째 원소에 넣는다.2. days 배열을 완전탐색하며, 앞 원소보다 작으면 count에 1만큼을 더하고, 아니라면 빼내는 코드를 작성한다. (이게 까다로움)

💡코드

from collections import deque

def solution(progresses, speeds):
    days = []
    for i in range(len(progresses)):
        p, s = progresses[i], speeds[i]
        if (100 - p) % s == 0:
            days.append((100 - p) // s)
        else:
            days.append((100 - p) // s + 1)
            
    answer = []     
    today = days[0]
    count = 1
    for i in range(1, len(days)):
        if days[i] > today:
            answer.append(count)
            today = daysa[i]
            count = 1
        else:
            count += 1
    answer.append(count)
    return answer

 

💡 오답 풀이

처음에 deque, queue로 풀려고 했는데 잘 안되더라..

💡 다른 풀이

나는 days 원소를 만들 때1)나누어 떨어지는 경우(나머지가 0인 경우)2)나누어 떨어지지 않는 경우(나머지가 0이 아닌 경우)두 가지로 나누어서 코드를 작성했다.

그런데 반올림 함수를 사용하면 10.00 -> 10, 10.10 -> 11이 되니까 경우의 수를 나눌 필요가 없다.

days.append(math.ceil((100 - p) / s))

math.ceil(반올림할 숫자) 함수를 사용하면 되고, 이를 사용하기 위해서는 import math가 필요하다.

 

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]

프로그래머스 상에서 제시하고 있는 다른 코드인데 완전 깔끔하다.

1. 빈 배열 Q 생성(Q의 원소는 [a, b] 형태로, a는 날짜가, b는 a날짜에 배포되는 기능의 개수가 들어간다.)

2. zip 함수를 사용해서 완전 빨라짐.. zip(progress, speeds)를 통해 두 배열의 i번째 원소를 한 번에 뽑아온다.

3. 반올림 함수를 안 쓰기 위해 -((p-100)//s)를 썼다. p < 100이므로 (p - 100)을 s로 나눈 몫은 음수가 된다. 맨 앞에 -를 붙여주어 음수를 양수로 바꿔준다.

예를 들어 p = 30, s = 30이면 -70 나누기 30의 몫은 -3, 나머지는 20이므로 -((p-100)//s) = -((30-100)//30) = -(-3) = 3이 된다.

4. Q가 비어있거나 맨 마지막 원소[a, b]의 a가 새로운 수 -((p-100)//s)보다 작으면 Q에 새로운 원소 [a, b]를 더해준다. 이 때 a는 -((p-100)//s)이고, b는 1이다.

5. 4의 여집합의 경우 Q의 맨 마지막 원소 [a, b]의 b에 1만큼을 더한다.

6. Q 속 모든 원소 [a, b] 중에서 b들만 반환한다.

💡 느낀점 or 기억할정보

아이디어는 간단한데 구현하기가 까다롭다!

days 배열 만드는 건 쉬웠는데, 그 아래 answer 배열 만드는게 어려웠다.