스택/큐 연습문제: 기능개발

문제

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

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

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

제한 조건

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

입출력 예

progresses = [93, 30, 55]

speeds = [1, 30, 5]

return = [2, 1]

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

나의 풀이

먼저 들어온 작업부터 끝내서 내보내게 되는 First-In First-Out 방식의 큐와 같은 자료구조를 가진 문제다.

리스트에서 첫 번째 값을 확인(peek)하여 값이 100 이상일 경우 리스트에서 꺼내고(pop), 그 다음 값을 확인하는 작업을 반복하면 될 것이라고 생각했다.

그 결과 다음과 같은 코드를 작성하게 되었다:

def solution(progresses, speeds):
    answer = []
    release = 0
    while len(progresses) > 0:
        if progresses[0] < 100:
            if release == 0:
                for i in range(0, len(progresses)):
                    progresses[i] = progresses[i]+speeds[i]
            else:
                answer.append(release)
                release = 0
        else:
            progresses.pop(0)
            speeds.pop(0)
            release += 1
            if len(progresses) == 0:
                answer.append(release)
    return answer

• 우선 작업수가 0이 될 때까지 while 문을 통해 프로세스를 반복하도록 했다.
• 리스트 가장 첫번째 값을 확인하여 100보다 작을 경우 진도를 나가도록 하고, 첫번째 값이 100 이상일 경우 작업이 완료된 것이므로 작업 리스트와 진도율 리스트의 첫번째 값을 둘 다 내보내고(pop) 배포된 기능 수(release)에 1을 누적해 주었다.
• 완료된 작업을 내보낸 다음 그 뒤에 오는 작업을 확인하여 100 이상일 경우 내보내기를 반복하고, 100 미만이면 누적된 release 값을 answer에 삽입한다.
• 만약 리스트 첫번째 값이 100 이상인데 더 이상 확인할 작업이 그 뒤에 없을 경우 바로 현재까지 누적된 release 값을 answer에 삽입시키고 while 반복문이 종료된다.

중첩 if 문을 써서 풀은 점이 아쉽다. elif 를 사용해서 조건들을 더 깔끔하게 나눴을 수도 있었을텐데 조건의 우선순위에 따라 결과가 달라지는 경우가 생기기도 하고, 리스트에 값이 하나만 남은 상황에서의 결과 반영이 바뀌는 경우도 있어서 코드를 반복해서 수정하다보니 이런 결과가 나오게 되었다.

다른 사람들의 풀이

def solution(progresses, speeds):
    print(progresses)
    print(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

나는 스택/큐 자료구조 문제라는 점에 너무 심취해서 put, peek, pop을 쓸 생각만 하고 다른 방법은 오히려 생각하지 못했던 것 같다. 그래서 작업 시간이 문제 풀이에 중요한 요소가 될 것이라고 생각하지 못했는데, 이 분은 time이라는 변수를 만들어서 작업속도에 곱하는 방식으로 값을 비교한 점이 인상깊었다.

전체적으로 코드도 훨씬 깔끔하고, 나의 코드에서 작업 진도를 더하기 위해 사용된 for문이 이 풀이에서는 전혀 필요하지 않아 실행 속도도 훨씬 빠를 것으로 예상된다.

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]

또다른 풀이는 굉장히 수학적이어서 인상 깊었는데, 원리가 정확하게 이해되지는 않지만 zip() 을 통해 작업률과 속도를 합쳐서 계산하기 쉽도록 한 점과 Q 안에 각 작업 별로 작업이 끝나기까지 필요한 일수와 n일 째에 배포 가능한 기능 수를 다차원 리스트로 담아 낸 것이 신기했다.

그나저나 프로그래머스에서 이 코드와 정확하게 똑같은 방식으로 푼 사람들이 130명 이상이라는 점이 뭔가 의심스럽다. 복붙 아니고 진짜로 다 이렇게 푼다고? 진짜로?!