99클럽 코테 스터디 3일차 TIL + 스택/큐

문제

프로그래머스 기능개발

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

프로그래머스

 

코드

from collections import deque

def solution(progresses, speeds):
    progresses_que = deque(progresses)
    speeds_que = deque(speeds)
    answer = []

    while progresses_que:
        while progresses_que[0] < 100:
            for i in range(len(progresses_que)):
                progresses_que[i] += speeds_que[i]

        done = 0
        while progresses_que[0] >= 100:
            done += 1
            progresses_que.popleft()
            speeds_que.popleft()
            if not progresses_que:
                break

        answer.append(done)

    return answer

 

풀이

앞에 있는게 pop 되어야 하기 때문에 큐 구조를 사용하였다.

while progresses_que:
        while progresses_que[0] < 100:
            for i in range(len(progresses_que)):
                progresses_que[i] += speeds_que[i]

맨 앞의 업무의 진도율이 100 이상 될때까지 각 업무에 계속 업무속도를 더한다.

 

 done = 0
        while progresses_que[0] >= 100:
            done += 1
            progresses_que.popleft()
            speeds_que.popleft()
            if not progresses_que:
                break

맨앞부터 업무 진도율이 100 이상인것만 pop하며 pop할때마다 done += 1 한다. 이때 done은 업무 완료 변수다.

pop하다가 업무 진도율이 100 미만인걸 발견하면 while 문을 탈출한다.

업무를 모두 처리 했을때(모두 pop되어서 큐에 남은 업무가 없을때)도 while문을 탈출한다.

 

answer.append(done)

done을 answer 배열에 추가한다.

 

 

 

더나은 코드

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

if문은 시간복잡도에 큰 영향을 끼치지 않는다.

그래서 전 코드보다 시간복잡도가 더 낮아서 코드 실행 속도가 더 빠르다.

 

(전)

# 테스트 1 〉   통과 (0.02ms, 10.1MB)
# 테스트 2 〉   통과 (0.52ms, 10.2MB)
# 테스트 3 〉   통과 (0.56ms, 10.2MB)
# 테스트 4 〉   통과 (0.18ms, 10.3MB)

 

(후)

# 테스트 1 〉   통과 (0.02ms, 10.1MB)
# 테스트 2 〉   통과 (0.12ms, 10.2MB)
# 테스트 3 〉   통과 (0.07ms, 10.1MB)
# 테스트 4 〉   통과 (0.07ms, 10.1MB)

 

 

새롭게 배운점 / 느낀점

• 비슷한 로직으로 돌아가는 코드를 짜도, common case의 시간 복잡도를 어떻게 줄이냐에 따라 실행속도가 확연히 차이가 난다는걸 느꼈다. ( 테스트 3 케이스에서는 무려 8배나 차이가 난다)
• 앞으로 코드를 짤 때, common case가 무엇인지 포착하고 이를 어떻게 설계하면 시간복잡도를 낮출 수 있는지 고민하도록 노력해야겠다.
• 코더가 아닌 개발자가 되자