[프로그래머스 스택/큐]기능 개발 - Python3

문제

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

코딩테스트 연습 - 기능개발 | 프로그래머스

 

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

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

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

제한 사항

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

 

입출력

                progresses                                      speeds                                              return

[93,30,55]

[1,30,5]

[2,1]

알고리즘

def solution(progresses, speeds):
    # 정답을 담을 배열
    answer = []
    
    # 선입선출을 활용하기 위한 자료구조 Queue
    queue = []

    # progresses배열을 순회하면서, 각 원소를 배포까지 며칠이 남았는지를 나타내게끔 바꾼다. 
    for i in range(len(progresses)):
        progresses[i] = (progresses[i] - 100) * -1
        progresses[i] = progresses[i] / speeds[i]
        if progresses[i] % 1 != 0:
            progresses[i] = int(progresses[i]) + 1

    # progress배열을 하나씩 queue에 집어넣는다.
    for i in range(len(progresses)):
        # queue에 원소가 하나도 없다면, progress[i]를 집어넣고 continue한다. 
        if len(queue) == 0:
            queue.append(progresses[i])
            continue

        # queue에 원소가 2개 이상 있다면, 원소들 중 가장 큰 값을 temp_max에 저장한다. 
        temp_max = max(queue)
        
        # queue에 progresses[i]를 집어넣는다.
        queue.append(progresses[i])

        # 만약 새로 들어온 원소가 기존의 최대값인 temp_max보다 크다면, 
        if temp_max < progresses[i]:
            # 방금 들어온 원소를 제외한 나머지를 arr에 복사한다. 
            arr = queue[0:-1]
            # arr의 원소의 갯수를 answer배열에 append한다. 
            answer.append(len(arr))
            
            # 방금 들어온 원소를 제외하고 나머지 원소는 없애준다. 
            while len(queue) != 1:
                queue.pop(0)
    
    # queue에 남아있는 원소들의 갯수를 answer에 append한다. 
    answer.append(len(queue))
    return answer

progresses = [93,30,55]
speeds =  [1,30,5]
print(solution(progresses, speeds))

 

설명

선입선출 구조를 가진 queue 자료구조를 사용한다. 원하는 형태로 만든 progresses를 queue에 하나씩 집어넣으면서, 원하는 작업을 수행한다. 

1. progresses배열을 순회하면서, 각 원소들에서 100을 빼고 -1을 곱해준다.
2. 그 값을 speed[i]로 나눈 값을 할당한다. 
3. 만약 소수로 나온다면, 1을 더해서 정수로 만든다.
4. progresses배열의 원소들을 하나씩 queue에 append한다.
   1. 이 때, queue의 갯수가 0개라면 하나의 progresses[i]를 append하고 continue한다.
   2. 현재까지 queue에 들어있는 값 중 가장 큰 값을 temp_max에 저장한다
   3. queue에 progresses[i]를 append한다.
   4. temp_max와 progresses[i]를 비교해서, 만약 temp_max가 작다면 
      1. 방금 들어온 원소를 제외한 나머지, 즉 queue[0:-1]을 arr에 복사한다. (0부터 끝에서2번째 원소까지)
      2. arr의 원소의 갯수를 answer에 append한다.
      3. 방금 queue에 들어온 원소를 제외한 나머지를 모두 pop한다. 
5. queue에 남아있는 원소들의 갯수를 answer에 append한다. 

 

결과

원하는 값을 출력한다. 

 

후기

일단 원하는 형태로 입력을 고치는 것까지는 정말 쉽게 했다. 그리고 큐를 사용해야겠다는 것은 확실하게 알았지만, 어떻게 활용해야 할지 감이 전혀 안왔다. 그러다가, 스택을 사용해서 풀었던 '짝지어 제거하기' 문제가 생각이 났다. 주어진 데이터를 하나씩 스택에 넣으면서 원하는 작업을 하고 결과물을 리턴하는 방식으로 해결했는데, 그게 생각이 나서 마찬가지로 큐를 활용해 문제를 해결했다. max값을 구해놓고, 새로 들어온 값이 max값보다 클 경우 앞에 원소들의 갯수를 answer에 붙이는 것이 핵심이었는데, 내가 이걸 생각하다니 정말 뿌듯하다 ㅎㅎ.