[파이썬] 프로그래머스 - 더 맵게
2022. 5. 10. 20:05
Algorithm
📌 Heap Heap은 데이터를 정렬된 상태로 저장하기 위해서 사용하는 자료구조이다. 파이썬의 heapq 모듈은 이진트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공한다. min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은 값은 언제나 인덱스 0, 즉, 이진트리의 루트에 위치한다. 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다. 힙에 원소 추가 heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있다. 첫 번째 인자는 원소를 추가할 대상 리스트이며 두 번째 인자는 추가할 원소를 넘긴다. (heapq 모듈에..
[파이썬] 프로그래머스 - 주식가격
2022. 5. 5. 14:53
Algorithm
📌 풀이 문제를 이해하기는 어렵지 않다. 리스트의 처음부터 나머지 원소들을 비교해 가격이 떨어지지 않는 유지 시간을 기록하는 것이다. 처음에는 2중 for문을 생각했다. 하지만 2중 for문을 이용할 경우 첫 번째 원소는 상관없지만 두 번째 원소부터는 해당 원소 이전 원소와 비교하지 말아야 하는데 지속해서 이전 원소와도 비교하는 것을 해결할 수 없었다. 따라서 생각해 낸 방법이 prices가 사라질 때 까지 while문을 돌리고 prices의 가장 왼쪽 원소를 pop시켜 남아있는 prices의 원소들과 비교하는 것이다. 이렇게 된다면 2중 for문에서 발생하는 본인 이전 원소와 비교하는 경우를 해결할 수 있다. [1, 2, 3, 2, 3] 을 예로 들면 우선 1을 popleft 시키고 (deque를 이용..
[파이썬] 프로그래머스 - 다리를 지나는 트럭
2022. 5. 4. 12:29
Algorithm
📌 풀이 1 (테스트 케이스 5 시간 초과) 큰 생각의 흐름은 "큐를 다리라고 생각하고 공기(0)들을 미리 채운 다음에 매 시간마다 pop 하고 현재 다리 위의 무게에 따라 트럭을 push 하거나 공기(0)를 push 한다"이다. 우선 queue를 양방향에서 처리해야 하기 때문에 양방형 처리에 유리한 deque를 사용했다. 공기(0)들을 미리 채우기 위해 truck_bridge_deque = deque(bridge_length * [0]) 을 통해 truck_bridge_deque를 설정해준다. while len(truck_bridge_deque)를 통해 다리 위에 있는 트럭이 모두 사라질 때까지 while문을 반복한다. if문에서는 대기 중인 트럭 즉 truck_weights_deque가 존재하는지 여..
[파이썬] 프로그래머스 - 프린터
2022. 4. 17. 00:39
Algorithm
📌 Deque A Double-ended Queue Double-ended는 양 끝에 elements를 추가/삭제를 지원한다는 의미 한다. Deque 주요 함수 append() : deque의 right end에 요소 추가 appendleft() : deque의 lef end에 요소 추가 pop() : deque의 right end의 요소 삭제 popleft() : deque의 left end의 요소 삭제 뒤에서 추가/삭제는 덱과 리스트는 속도 차이가 없지만, 첫 번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생한다. 첫번째 원소를 삭제하면 그림처럼 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)이기 때문이다. 📌 풀이 핵심은 어떻게 location을 내가 인쇄를 요청한 원소에 ..
[파이썬] 프로그래머스 - 기능개발
2022. 4. 14. 23:47
Algorithm
📌 풀이 1 우선 remail_days라는 리스트를 만들어 준다. 이 리스트에는 progresses 에서 speeds를 나누어 준 값을 올림 한 값 즉 남은 작업일 수를 저장해준다. 이때 for 문을 이용하여도 되지만 간단히 쓰기 위해 labda 함수를 이용한다. 또한 올림 처리는 math 라이브러리의 ceil 함수를 이용했다. ramain_days = [] for i, j in zip(progresses, speeds): remain_days.append(math.ceil((100 - i) / j)) -> 람다식으로 전환 remain_days = list(map(lambda x: (math.ceil((100 - progresses[x]) / speeds[x])), range(len(progresses)..