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

https://programmers.co.kr/learn/courses/30/lessons/42586?language=pyth 

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

 

[93, 30, 55] → progresses

[1, 30, 5] → speeds

같이 구성이 되어 있을 때

각 기능마다 일이 처리될 수 있는 시간은 다음과 같이 분포한다

[7, 3, 9]

즉, 93% 일이 처리 된 기능의 경우 한번에 1만큼 처리를 하므로 총 7

30% 일이 처리 된 기능의 경우 한번에 30만큼 처리를 하므로 총 3

55% 일이 처리 된 기능의 경우 한번에 5만큼 처리를 하므로 총 9의 시간이 걸림

이러한 걸리는 시간을 계산하는 결과를 result라는 리스트에 담음 코드는 다음과 같음

 

result = [] # 시간 걸리는 결과를 담을 리스트
for i in range(len(progresses)) : 
	lim = 100 - progresses[i]
	get = 0 # 걸리는 시간 count
	while True : 
		get += 1
		if get*speeds[i] >= lim : 
			break
	result.append(get)

이렇게 걸리는 시간을 기반으로

문제는 각 베포마다 몇 개의 기능이 처리되는 지를 묻는 문제!

 

[7, 3, 9] 예제를 생각해봅시다

첫 번째 기능은 7일, 두 번째 기능은 3일인데 첫 번째 기능이 베포되기 전까지 두 번째 기능은 베포되지 않고 첫 번째 기능이 베포될 때 비로소 2번째 기능이 베포되므로 첫 베포때는 2

두 번째에는 9번이 걸리므로 두 번째 베포 때는 1이 걸림

 

즉, 그 때 그 때 Max값들에 따라 값을 누적하다 Max가 갱신되면 그 누적되는 값을 넣어주는 방식으로 동작

 

베포되는 수를 계산해주는 코드는 다음과 같음

 

accum = 1 # 누적값 변수
Max = result[0] # 초기 Max 설정
for i in range(1, len(result)) : 
	## Max값 갱신될 때
	if Max < result[i] : 
		answer.append(accum)
		accum = 1
		# 끝에 값이 Max가 아니면 갱신 -> 끝에 거의 경우 갱신을 할 필요 없음, 뒤에서 예외처리
		if i != len(result)-1 : 
			Max = result[i]
	else : 
		## Max 갱신이 안되는 경우
		accum += 1
		## 끝에 값인 경우 빼줘야지
		if i == len(result)-1 : 
			answer.append(accum)
## for문의 첫번째 if 조건에 해당되는 경우, 즉 맨 마지막 수가 Max인 경우, 
## 마지막 Max가 베포되는 경우도 추가해주어야 하므로
if Max < result[len(result)-1] : answer.append(1)
return answer

총 코드는 다음과 같음

def solution(progresses, speeds):
    answer = []; result = []; # 시간 걸리는 결과를 담을 리스트
    accum = 1 # 누적값 변수
		## 걸리는 시간 목록 계산 루프 --> O(n) while 반복문이 큰 시간 cost가 없음
    for i in range(len(progresses)) : 
        lim = 100 - progresses[i]
        get = 0 # 걸리는 시간 count
        while True :
            get += 1
            if get*speeds[i] >= lim :
                break
        result.append(get)
    Max = result[0] # 초기 Max 설정
		## 베포되는 수를 계산하는 루프 -> O(n)
    for i in range(1, len(result)) : 
				## Max값 갱신될 때
        if Max < result[i] : 
            answer.append(accum)
            accum = 1
						# 끝에 값이 Max가 아니면 갱신 -> 끝에 거의 경우 갱신을 할 필요 없음, 뒤에서 예외처리
            if i != len(result)-1 : 
                Max = result[i]
		    ## Max 갱신이 안되는 경우
        else : 
            accum += 1
						## 끝에 값인 경우 빼줘야지
            if i == len(result)-1 : 
                answer.append(accum)
		## for문의 첫번째 if 조건에 해당되는 경우, 즉 맨 마지막 수가 Max인 경우, 
		## 마지막 Max가 베포되는 경우도 추가해주어야 하므로
    if Max < result[len(result)-1] : answer.append(1)
    return answer

최종 계산한 Time Complexity O(n)