첫 주차에 본 알고리즘 테스트!
문제를 풀진 못했지만, 문제를 푸는 멋진 방법들을 배웠다!
문제 1. https://programmers.co.kr/learn/courses/30/lessons/42586
프로그래머스 레벨 2 문제다!
각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
스택을 이용하여 풀어야 하는 문제!
문제 포인트 1 : 0번째 자리에 있는 애가 다 개발되어야만 그 뒤에 있는 애도 배포할 수 있다.
문제 포인트 2 : 주어지는 배열은 개발속도, 개발진척도 2개이다.
문제 포인트 3 : 개발속도는 1일마다 카운트 된다.
문제포인트 1은 가장 위에 쌓은 애가 먼저 나가야 하는 스택이라는 유형을 추천하는 부분이다.
2는 내가 고려해야 할 반복문의 종류.
단순 순서 비교가 아니라 컨텐츠의 증감을 비교해야 하므로 포문 말고 while문으로 전체를 덮어야 한다!
가장 쉬운 브레이크조건은 안에있는거 pop으로 빼면서 주어진배열의 길이 > 0으로 걸어주는거
3은 시간적인 알고리즘인데 정말 놀라운 발견이었다!
카운트를 1일마다 초기화한다는 그 발상이 코드의 길이를 천재적으로 줄여주었다.
내가 한 생각은 아니지만 ㅠㅠ
전체 코드
1) 스택을 이용한 풀이
def solution(progresses, speeds):
stack = []
time = 0
count = 0
while len(progresses) > 0:
if progresses[0] + speeds[0] * time >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
stack.append(count)
count = 0
time += 1
stack.append(count)
return stack코드를 보면 두개의 값을 받아오고, 스택으로 쓸 빈 배열이 하나
정답에 제출해야 할 하루 갯수 카운트 하나
그리고 멋진 시간별로 끊어주는 카운트가 하나 있다!
코드의 흐름
와일문은 progresses의 길이가 0이 될때까지 돈다.
첫번째 if문은 개발속도 + 개발진척도 * 시간 >= 100이다.
당연히 첫 몇번의 반복에서는 패스한다.
두번째 if문은 첫번째 if의 else에 걸린 애인데 현재 카운트가 0 이상인지 보는거다.
당연히 첫번째가 걸린적이 없으면 걸리지 않는다.
그래서 가장 먼저 걸리는건 두번째 if문의 else -> time카운트를 하나 증가시켜주는 코드다.
하루가 지나간거다.
반복문 끝의 append는 count 변수에 값이 들어오지 않으면 작동하지 않는다.
낼게 없으니까.
며칠 지나면 슬슬 첫번째 개발은 완료된다.
왜냐하면 progresses와 speeds는 변하지 않았지만
시간의 곱셈이 들어갔기 때문에!
대단해!
스택의 맨 위 = 0번째는 두번째 개발로 맞추어진다.
또한 반복문의 마지막코드에 의해 카운트가 1 올라간다!
두번째 개발부터는 이미 시간이 곱해져 있는 상태이기 때문에 빨리 빨리 진척될 수 있다.
이제 하루에 몇개 할 수 있는지를 적으라고 했으니까 그걸 출력해야 한다.
여기서 두번째 if문이 나온다.
두번째 if문에서는 개발속도 + 개발진척도 * 시간 >= 100이 되지 않았는데
카운트가 0 이상이라면 현재 카운트의 값을 stack에 append하고 카운트를 초기화시켜준다!
놀라워!
그리고 찾다보니 데크로 풀이한 것도 찾았다.
데크를 쓰는 법은 생각보다 어렵지 않았다.
맨 앞에 있는걸 빼야 할때는 꼭 데크로 빼는 습관을 들여야겠다.
그래야 시간복잡도... 그게 줄어든다고 한다.
2) 데크를 이용한 풀이
전체코드
from collections import deque
def solution(progresses, speeds):
stack = []
time = 0
count = 0
progresses = deque(progresses)
speeds = deque(speeds)
while len(progresses) > 0:
if progresses[0] + speeds[0] * time >= 100:
progresses.popleft()
speeds.popleft()
count += 1
else:
if count > 0:
stack.append(count)
count = 0
time += 1
stack.append(count)
return stack맨 위에 데크를 임포트하고
pop(0) 대신에 popleft()를 써주면 맨 위에꺼가 나간다!
신난다!
프로그래머스에 제출하고 나니 다른사람이 다른 방식으로 푼 것들도 있었지만 완전히 이해할 수는 없었다 ㅠㅠ
열심히 하다보면 나아지겠지!
