[Programmers] Python 프로그래머스 기능개발 Level 2

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

코딩테스트 연습 - 기능개발

 

프로그래머스의 분류에도 나와 있듯이 큐를 사용하면 쉽게 풀 수 있는 문제이다.

 

스택과 큐에 대해 익숙하지 않거나 까먹었다면 먼저 이전 포스팅을 참고하여 이해하고 오는 것을 추천한다.

 

https://khsung0.tistory.com/14?category=1038750 

[알고리즘] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python)

 

문제 풀이

---

눈여겨봐야 할 점은 5가지다.

 

1. 작업의 개수는 100개 이하
2. 작업 진도는 100 미만의 자연수
3. 작업 속도는 100 이하의 자연수
4. progresses의 순서대로 배포한다.
5. 배포는 하루에 한 번만 이루어진다.

 

문제를 보자마자 떠올린 생각은 day를 하루씩 증가시키면서 progresses 리스트에 speeds 리스트의 원소를 계속 더하고 progresses의 길이가 0이 될 때까지 같은 날에 0번째 인덱스의 원소가 100 이상이면 pop 하면서 카운트하여 answer에 추가하는 방식이었다.

 

애초에 작업의 개수가 100개 이하고 작업 진도가 1, 작업 속도가 1일 때 최대 99일이므로 Input이 작아 가능성은 있어 보였다.

 

하지만 Python의 pop함수에서 0번째 인덱스를 제거하는 pop(0)은 O(n)의 시간 복잡도를 가지므로 원소를 제거하는 과정에서 추가적으로 불필요한 연산이 생기기에 상당히 비효율적인 방식이라 다른 방법을 생각해봤다.

 

그 결과 굳이 매번 원소들을 더하는 게 아니라 day를 증가시키면서 같은 day일 경우를 카운트하여 answer에 추가하고 기존의 리스트에 대한 변경 없이 현재 어떤 인덱스를 가리키는지 알려주는 curr_index를 선언한다면 매번 원소를 제거할 때 드는 시간 복잡도도 없어질 것이라 판단하였다.

 

전체 코드를 통해 설명하면 이해가 더 빠를 것이다.

 

def solution(progresses, speeds):
    answer = []
    day=0           #개발 일수
    curr_index=0    #현재 작업 Index

    #작업 Index를 0번 부터 끝까지 반복
    while curr_index<len(progresses):

        #현재 작업이 100% 넘을 때까지 day 증가
        while progresses[curr_index]+speeds[curr_index]*day<100:
            day+=1

        #완료된 작업 개수 카운트
        cnt=0

        #완료된 작업 카운트
        while curr_index<len(progresses) and progresses[curr_index]+speeds[curr_index]*day>=100:
            cnt+=1
            curr_index+=1
        answer.append(cnt)
    return answer

 

7번째 줄을 통해 progresses 리스트를 전체 반복하고 10번째 줄을 통해 현재 작업이 100%가 될 때까지 day를 증가시킨다.

 

day를 찾으면 같은 날일 때 몇 개의 작업을 배포할 수 있는지 세기 위해 14번째 줄에 cnt를 선언하여 0으로 초기화한다.

 

초기화된 cnt를 기반으로 17번째 줄에서 배포 가능한 작업들을 세며 curr_index를 증가시킨다.

 

이때 while문에서 curr_index<len(progresses)를 먼저 선언한 이유는 curr_index가 증가할 때 progresses의 리스트 범위를 벗어나 Index Error를 일으킬 수 있기 때문이다.

 

프로그래밍 언어에서 조건을 판단할 때 앞에 있는 조건이 False라면 뒤에 있는 조건을 확인하지 않기 때문에 이처럼 Index Error를 방지하는 조건이나 시간 복잡도를 최대한 줄일 수 있는 조건은 되도록이면 앞에 쓰는 습관을 들이자.

 

마지막으로 카운트한 작업 수를 answer에 추가하면 끝이다.

 

결과 화면

 

이렇게 구현한 방식은 리스트의 원소를 제거하는 등 불필요한 연산을 줄였기 때문에 day를 증가시키는 연산(최대 99번), progresses 리스트를 탐색하는 연산(최대 100번)을 하면 최대 약 10,000번의 연산을 한다.

 

엄밀히 말하자면 큐로 푼 게 아니라 리스트의 인덱스 접근을 통해 풀었고 처음에는 상당히 비효율적인 방식을 생각했었다.

 

항상 문제의 조건을 정확히 파악하여 자신이 생각한 방식의 시간 복잡도를 계산해보고 보다 더 효율적인 방식이 있는지 끊임없이 고민하는 습관이 상당히 중요한 것 같다.