프로그래머스 코딩테스트 연습, 레벨 2에 있는 "기능개발" 문제다.
여기도 재밌는 문제가 많은 것으로 기억해서 간만에 하나 풀어보기로 하였다.
문제는 아래(progresses, speeds)와 같은 입력을 받았을 때, 한번의 배포마다 몇개의 기능을 배포할 수 있는지를 구하는 것이다. 이 때, progresses와 speeds는 각각 작업의 진도와 하루동안 개발되는 작업의 속도를 나타내는 정수 배열이다.
| progresses | speeds | return |
|---|---|---|
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
| [95, 90, 99, 99, 80, 99] | [1, 1, 1, 1, 1, 1] | [1, 3, 2] |
그리고 신경써야할 조건이 몇 있다.
- 모든 기능 개발은 동시에 이루어지며 배포는 하루가 끝났을 때에 가능하다.
- 하나의 기능 개발이 완료되는 것은 작업의 진도가 100을 넘었을 때이다.
- 뒤의 기능이 먼저 개발되더라도 선행하는 기능의 개발이 완료되었을 때만 배포가 가능하며, 앞의 기능과 함께 배포된다.
예를 들어 첫번째 테스트 케이스에선, 첫번째 기능이 7일 후에 배포가능하고 두번째 기능이 3일 후, 마지막 기능은 9일 후에 가능해진다.
그래서 조건에 의해 첫번째와 두번째 기능은 7일 후에 함께 배포되고, 9일 후에 마지막 기능 하나가 배포된다. ([2, 1])
from collections import deque
def solution(progresses, speeds):
deq_p = deque(progresses)
deq_s = deque(speeds)
answer = []
while(len(deq_p) > 0):
count = 0
for i in range(len(deq_p)):
speed = deq_s.popleft()
deq_p.append(deq_p.popleft()+speed)
deq_s.append(speed)
for i in range(len(deq_p)):
if(deq_p[0] >= 100):
deq_p.popleft()
deq_s.popleft()
count += 1
if count > 0:
answer.append(count)
return answer큐를 이용해 해결하고자, 각 정수 배열을 deque로 바꾸고 모든 기능의 작업이 완료될 때까지(큐에 원소가 없어질 때까지) 모든 완료되지 않은 기능의 진도에 대응하는 작업 속도만큼 더해주었다. 그리고 매일 끝날 때마다 개발이 완료된 기능이 존재하면 순서대로 몇개인지 확인해서 큐에서 제거해주도록 하였다.
사실 반드시 큐로 풀어야만 효율적인 문제도 아니고, 내가 작성한 코드는 루프도 많아서(큐를 사용한 것이 무색하게 오래 걸림...) 다른 분들의 코드를 보면서 많이 반성하게 되었다. 조금 슬프긴 했지만, 앞으로 더 신경써서 구현해보는 것으로 하고.
이 문제를 풀면서 python의 deque 컨테이너 데이터형에 대해 알아본 것을 정리하고자 한다.
deque(데크라고 읽음)는 "double-ended queue"의 줄임말로 양방향 큐, 즉 스택과 큐 둘 모두로 사용가능하다.
데크는 양 끝에서의 추가와 삭제 시 O(1)의 성능으로 매우 효율적이다.
"제일 먼저 들어간 것 또는 나중에 들어간 것의 저장과 삭제"가 주로 필요할 때 list 보다는 deque를 사용하자.
| 메서드 | 설명 |
|---|---|
| append(x) | 데크의 오른쪽에 x를 추가합니다. |
| appendleft(x) | 데크의 왼쪽에 x를 추가합니다. |
| clear() | 데크에서 모든 요소를 제거하고 길이가 0인 상태로 만듭니다. |
| copy() | 데크의 얕은 복사본을 만듭니다. (shallow copy와 deep copy에 관해선 추후 포스팅) |
| extend(iterable) | iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장합니다. |
| extendleft(iterable) | iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장합니다. |
| pop() | 데크의 오른쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다. |
| popleft() | 데크의 왼쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다. |
| reverse() | 데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환합니다. |
| rotate(n=1) | 데크를 n 단계 오른쪽으로 회전합니다. n이 음수이면, 왼쪽으로 회전합니다. 오른쪽으로 회전하는 것은 d.appendleft(d.pop()), 왼쪽으로 회전하는 것은 d.append(d.popleft())와 같음. |
추가적으로 len(deque)로 원소의 개수를 확인할 수 있고, deque[0]으로 원소의 제거 없이 첫 원소를 확인할 수 있다.
인덱스를 통한 메모리 접근도 가능하지만, 그럴 때는 그냥 list를 사용하는 것이 더 좋을 것으로 보인다.
참고 자료
