Queue

백준 1021번 문제 바로가기 deque을 이용한 풀이 deque(덱)을 이용해서 문제를 해결했다. deque는 일명 양방향 queue인데 queue.pop(0)으로도 맨 앞의 요소를 꺼낼 수 있지만 그보다는 deque.popleft()을 사용하는 편이 시간 소요가 적다.(더 직관적이기도 하고) 어떤 방향(오른쪽/왼쪽)으로 회전하는 것이 더 유리한지 판단하는 것만 잘 고려해주면 비교적 쉽게 해결 가능했다. # 입력 import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) arr = map(int, sys.stdin.readline().split()) count = 0 queue = deque([i+1 for i in range(n)]) # 처리 for i in arr: if queue[0] == i: queue.popleft() else: from_left = queue.index(i) from_right = len(queue) - queue.index(i) - 1 if from_left <= from_right: for _ in range(from_left): queue.append(queue.popleft()) count += from_left queue.popleft() else: for _ in range(from_right): queue.appendleft(queue.pop()) count += from_right + 1 queue.pop() print(count)

다리를 지나는 트럭 문제 바로가기 나의 풀이 from collections import deque def solution(bridge_length, weight, truck_weights): time = 0 bridge = [0] * bridge_length bridge_sum = 0 bridge = deque(bridge) truck_weights = deque(truck_weights) while truck_weights: bridge_sum -= bridge[-1] bridge.pop() time += 1 if bridge_sum + truck_weights[0] <= weight: bridge.insert(0, truck_weights.popleft()) else: bridge.insert(0, 0) bridge_sum += bridge[0] time += bridge_length return time 고수의 풀이 import collections DUMMY_TRUCK = 0 class Bridge(object): def __init__(self, length, weight): self._max_length = length self._max_weight = weight self._queue = collections.deque() self._current_weight = 0 def push(self, truck): next_weight = self._current_weight + truck if next_weight <= self._max_weight and len(self._queue) < self._max_length: self._queue.append(truck) self._current_weight = next_weight return True else: return False def pop(self): item = self._queue.popleft() self._current_weight -= item return item def __len__(self): return len(self._queue) def __repr__(self): return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue)) def solution(bridge_length, weight, truck_weights): bridge = Bridge(bridge_length, weight) trucks = collections.deque(w for w in truck_weights) for _ in range(bridge_length): bridge.push(DUMMY_TRUCK) count = 0 while trucks: bridge.pop() if bridge.push(trucks[0]): trucks.popleft() else: bridge.push(DUMMY_TRUCK) count += 1 while bridge: bridge.pop() count += 1 return count def main(): print(solution(2, 10, [7, 4, 5, 6]), 8) print(solution(100, 100, [10]), 101) print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110) if __name__ == '__main__': main() 출처 ...

백준 1158번 바로가기 나의 풀이 from collections import deque import sys n, k = map(int, sys.stdin.readline().split()) q = deque([i+1 for i in range(n)]) n = 1 ans = [] while q: temp = q.popleft() if n == k: ans.append(temp) n = 1 else: q.append(temp) n += 1 print('<', end='') for i in ans[:-1]: print(i, end=", ") print(f'{ans[-1]}>') CODE REVIEW queue을 이용한 요세푸스 문제의 해결. 원형 array를 활용하는 방법도 있긴 하지만, 개인적으로 queue 활용하는 편이 깔끔해 보인다. 마지막에 출력하는 부분이 의외로 손이 많이 갔는데, for문을 사용하지 않고 싶다면 print(*ans, sep=', ', end='')로 해결하는 방법도 있다.

주식가격 문제 바로가기 이중 for문을 이용한 풀이 def solution(prices): updown = [0] * len(prices) for i in range(len(prices)): for j in range(i+1,len(prices)): updown[i] += 1 if prices[i] > prices[j]: break return updown queue을 이용한 풀이 def solution(prices): updown = [] for i in range(len(prices)): from collections import deque current = prices[i] check = deque(prices[i:]) count = 0 while check: temp = check.popleft() count += 1 if current > temp: break updown.append(count-1) return updown 다른 사람들의 풀이 구경하기 def solution(prices): stack = [] answer = [0] * len(prices) for i in range(len(prices)): while stack != [] and stack[-1][1] > prices[i]: past, _ = stack.pop() answer[past] = i - past stack.append([i, prices[i]]) for i, s in stack: answer[i] = len(prices) - 1 - i return answer 출처 CODE REVIEW 이중 for문 풀이가 간편하지만, 실상 데이터가 늘어나면 늘어날수록 시간이 많이 소요된다. 시간복잡도:O(N^2) queue을 이용한 풀이도 시도했는데, queue를 활용했다는 점만 다르지 실상 시간복잡도가 O(N^2)라서 시간초과로 효율성에서 꽝이었다. 다른 사람들의 풀이도 구경해봤는데, 조건문을 이용해서 구하고 count을 1씩 늘려나가는 대신, 범위로 한번에 구해서 효율성을 개선시켰다는 점을 깨달았다. 굳이 필요하지 않은 정보는 메모리절약을 위해 저장하지 말자!

프로세스 문제 바로가기 나의 풀이 def solution(priorities, location): from collections import deque q = deque(priorities) count = 1 while q: m = max(q) temp = q.popleft() location -= 1 if location < 0: if temp < m: location = len(q) q.append(temp) else: return count else: if temp < m: q.append(temp) else: count += 1 다른 사람들의 풀이 구경하기 def solution(priorities, location): queue = [(i,p) for i,p in enumerate(priorities)] answer = 0 while True: cur = queue.pop(0) if any(cur[1] < q[1] for q in queue): queue.append(cur) else: answer += 1 if cur[0] == location: return answer 출처 CODE REVIEW 첫 번째 풀이에서는 deque을 이용해서 풀어내었다. 원소를 맨 앞에서부터 하나씩 꺼내면서 최대인지 아닌지 따져주면 쉽게 결과를 얻을 수 있다. 다른 사람들의 풀이 구경하기 같은 경우, 논리는 비슷하지만 특이하게 any()를 이용해서 풀어내었다. 확실히 식이 깔끔해지긴 한듯! * 다만, 이 경우 priorities의 길이가 아주 길어질수록 소요시간이 급격하게 증가하기 때문에 그렇게 추천하진 않는다…