알고리즘 연습 프로그래머스 스택 - 큐 기능개발 문제 풀이

사용 언어: python3

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

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

글로 쓴 풀이 선입 선출의 queue 구조를 활용 하면 쉽게 풀릴 것 같다.

 

# 제일 처음 작성한코드 목적  달성 위주
def solution(progresses, speeds):
    queue = []
    answer = []
    while True:
        if len(progresses) == 0:
            break;
        for i in range(len(progresses)):
            count = 0
            progresses[i] += speeds[i]
            lens = len(progresses)
        for j in range(lens):
            if progresses[0] >= 100:
                count += 1
                progresses.pop(0)
                speeds.pop(0)
            if j == lens -1 and count != 0:
                answer.append(count)
        
    return answer
print(solution([93, 30, 55],[1, 30, 5]))

#return 2,1

위 코드로 테스트 결과 통과! 그러나 while true 문 안에 반복문이 두개나 있다니.. 시간 복잡도를 구해보자

big-O 표기법을 통해서 구해보면 len(answer) * 2n 의 시간이 걸린다 (이게 맞나..?) 틀렸다면 덧글로 알려주세요!

 

코드를 조금 개선 해보도록 하겠습니다.

곰곰히 생각을 해보니, progresses[0] 값이 100을 넘냐 넘지 않냐를 캐치하는게 가장 중요합니다. 즉, 1번 & 2번 포문을 한 번씩 돌 필요가 없는 것이죠. 이제 다음과 같이 개선 할 수 있을 것 같습니다.

# 첫 번째 리팩토링
def solution(progresses, speeds):
    queue = []
    answer = []
    day = 0
    while True:
        lens = len(progresses)
        count = 0 
        day += 1
        for i in range(lens):
            if progresses[0] + day * speeds[0] >= 100:
                count += 1
                progresses.pop(0)
                speeds.pop(0)
            if i == lens - 1  and count > 0:
                answer.append(count)
        if len(progresses) == 0:
            break;
        
        
    return answer
print(solution([93, 30, 55],[1, 30, 5]))

#return 2,1

두번 돌던 포문을 한번으로 줄였습니다!  

자, 그런데 if len(progresses) == 0: break 이 코드가 웬지 모르게 거슬립니다. while 문과 결합 할 수는 없을까요?

# 두 번째 리팩토링
def solution(progresses, speeds):
    queue = []
    answer = []
    day = 0
    while len(progresses) > 0:
        lens = len(progresses)
        count = 0 
        day += 1
        for i in range(lens):
            if progresses[0] + day * speeds[0] >= 100:
                count += 1
                progresses.pop(0)
                speeds.pop(0)
            if i == lens - 1  and count > 0:
                answer.append(count)
        
        
    return answer
print(solution([93, 30, 55],[1, 30, 5]))

#return 2,1

최종 버전 입니다. while 문을 종료 시키는 if문을 while 구절과 통합 하였습니다.

 

오늘은 프로그래머스의 스택 - 큐 기능개발 문제 풀이를 해 보았습니다. 

단순히 문제를 해결하기만 하는 것 보다

조금 더 나은 방법으로 해결하기 위해서 고민 하는 과정이 더 즐거운 것 같습니다.

 

감사합니다