알고리즘 문제 #2 - 기능개발

두 번째 알고리즘

지난번에 이어 이번에도 알고리즘 문제를 풀어보았다. 이번 문제는 제목이 기능개발이다.

지난 문제와는 달리 그래도 빠르게 이해할 수 있었던 것 같다. 먼저 문제를 이해하고, return 값과 동일한 결과가 나오도록 코드를 짜보았다.

문제를 이해한 대로 보자면, prossess에 진행률에 따른 숫자 리스트가 입력된다. 그리고 speeds에는 작업 속도가 입력된다. 진행률이 100이 되면 출력은 가능하지만, 리스트 앞에 있는 progress가 완성되어 있지 않다면, 뒤에 있는 progress는 배포될 수 없다.
FIFO 방식인 큐 문제인 것 같다.

먼저 속도에 따라서 결과물이 나올 수 있기까지 얼마나 많은 시간이 걸리는지 알아보아야 했다.
math 함수를 이용해 나누었을 때, 딱 떨어지지 않는 소수점은 그 위의 정수로 변환하는 ceil 메서드를 사용했다.

import math

for i in range(len(progresses)):
	days.append(math.ceil((100-progresses[i])/speeds[i]))

그리고 이 수를 days라고 하는 리스트를 선언해 append로 저장하는 방식으로 코딩을 진행해보았다. 결과는??

테스트 결과는 모두 성공하였다. 됐다! 하면서 코드를 제출했는데 웬걸..? 테스트 1, 8, 11을 뺀 모든 결과가 실패하였다.

'뭐지? 뭐가 틀렸지? 내가 뭘 잘못 이해했을까?'

다시 생각해보았다. 여러 경우를 따져서 들어맞지 않는 경우를 찾아야 했다. 뒤에 있는 작업물은 모두 100이지만, 맨 앞에 있는 작업물 때문에 배포가 늦어지는 경우라면 오류가 발생할 수 있었다.

이런 예외를 생각해 코드를 다시 짜보았다.

import math

def solution(progresses, speeds):
    
    days = [] # progresses를 speeds의 속도로 처리하는 데 걸리는 각각의 시간을 담는 리스트
    answer = [] # 처리되는 배포 양?을 포함하는 리스트
    l = 0 # 위치를 반환하는 변수
    w = True #while문을 빠져나오기 위한 변수

    for i in range(len(progresses)): #math 함수의 ceil을 이용해 나누기의 소수점을 바로 위의 정수로 변환해 필요한 일 수 계산
        days.append(math.ceil((100-progresses[i])/speeds[i]))
    
    while w == True:

        for i in range(l,len(progresses)): #l부터 끝까지 탐색
            if days[l] < days[i]: #temp[l]보다 큰 수가 있는지 탐색
                answer.append(i-l)  #있다면 l - i인 값을 answer에 저장
                l = i #큰 수가 있는 i부터 다시 탐색
                break
            elif (i == len(progresses)-1) and (days[l] >= days[i]): #끝까지 갔는데 큰 수가 없을 경우
                answer.append(len(progresses)-l) #progresses의 전체 길이에서 l을 뺌.
                w = False #while문 탈출을 위해 w를 False로 변경
                break

    return answer

1시간 동안 코드와 씨름하면서 만든 코드를 다시 programmers에 집어넣고 돌려보았다.

결과는 대성공이다.

이번 문제는 너무 비꼬아서 생각하면서 코딩이 좀 오래 걸리지 않았나 싶다. 아직은 큐, 스택 문제가 적응이 쉽지가 않다. 더 빠르게 문제를 해결하기 위해서 많은 실습 문제를 접해보아야 할 것 같다.