[프로그래머스] Level2_기능개발(스택/큐)

문제 유형

스택/큐

 

문제

프로그래머스

 

문제풀이

1차시도(27.3)

from collections import deque

def count_return(percent, speed):
    ans = 0
    while percent[0] <= 100:
        for i in range(len(percent)):
            percent[i] += speed[i]
    
    for i in range(len(percent)):
        if percent[0] >= 100:
            percent.popleft()
            ans += 1
        else:
            break
    
    return ans, percent, speed

def solution(progresses, speeds):
    answer = []
    percent = deque(progresses)
    speed = deque(speeds)
    
    while len(list(percent)) > 0:
        ans, percent, speed = count_return(percent, speed)
        answer.append(ans)
        
    return answer

 

2차시도(90.9)

from collections import deque

def count_return(percent, speed):
    ans = 0
    while percent[0] <= 100:
        for i in range(len(percent)):
            percent[i] += speed[i]
    
    for i in range(len(percent)):
        if percent[0] >= 100:
            percent.popleft()
            speed.popleft()		# speed도 같이 제거하기!!!
            ans += 1
        else:
            break
    
    return ans, percent, speed

def solution(progresses, speeds):
    answer = []
    percent = deque(progresses)
    speed = deque(speeds)
    
    while len(list(percent)) > 0:
        ans, percent, speed = count_return(percent, speed)
        answer.append(ans)
        
    return answer

 

3차 시도(통과)

• 시간복잡도 적은 deque로 선언
• percent 맨 앞이 100 이상이 되도록 speed 더하기(부호 주의)
• percent 맨 앞이 100 이상이면, popleft로 하나씩 제거(percent, speed 둘 다)
   * popleft는 deque 명령어
• percent 길이 0될때까지 반복

from collections import deque

def count_return(percent, speed):
    ans = 0
    
    # 리스트의 맨 앞이 100이상이 되도록 speed 더하기
    while percent[0] < 100:		# 부호!! 100 미만일때까지만 더하기
        for i in range(len(percent)):
            percent[i] += speed[i]
    
    # 리스트의 맨 앞이 100이상이면 앞에서부터 하나씩 제거(percent, speed 둘 다)
    for i in range(len(percent)):
        if percent[0] >= 100:
            percent.popleft()
            speed.popleft()
            ans += 1
        else:
            break		# break 없으면 인덱스 오류 발생
    
    return ans, percent, speed

def solution(progresses, speeds):
    answer = []
    # 시간복잡도 적은 dequeue 선언
    percent = deque(progresses)
    speed = deque(speeds)
    
    # percent 길이가 0될때까지 반복
    while len(list(percent)) > 0:
        ans, percent, speed = count_return(percent, speed)
        answer.append(ans)
        
    return answer

 

다른 사람들 풀이

1)  time 조건문

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

 

2)  ceil 함수 이용

• ceil : 값 올림하기
• try-except 문으로 IndexError 해결

파이썬 math 모듈 ceil( ), floor( ) 함수 / 실수를 올림, 내림하여 정수를 반환하는 함수

from math import ceil

def solution(progresses, speeds):
    daysLeft = list(map(lambda x: (ceil((100 - progresses[x]) / speeds[x])), range(len(progresses))))
    count = 1
    retList = []

    for i in range(len(daysLeft)):
        try:
           # 리스트 앞이 남은 날짜 적을때
            if daysLeft[i] < daysLeft[i + 1]:
                retList.append(count)
                count = 1
            # 남은 날짜가 같을 때
            else:
                daysLeft[i + 1] = daysLeft[i]
                count += 1
        # 인덱스 에러 해결
        except IndexError:
            retList.append(count)

    return retList

 

3)  풀이 유사

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

 

4) 유사

from collections import deque

def solution(progresses, speeds):
    answer = []
    progresses = deque(progresses)
    speeds = deque(speeds)
    while progresses:
        a=0
        while 1:
            if progresses[0] >= 100:
                a+=1
                progresses.popleft()
                speeds.popleft()
                if len(progresses) == 0 and a >0:
                    answer.append(a)
                    break
            else:
                if a>0:
                    answer.append(a)
                for i in range(len(progresses)):
                    progresses[i]+=speeds[i]
                break
    return answer

 

리뷰

 - 큐에 대한 기본적인 개념 이해

파이썬에서 큐(queue) 자료 구조 사용하기

 - 인덱스 오류는 try-except문으로 해결할 수 있음

 - ceil : 숫자 올림하기