💻 문제 - Lv.2
2022 KAKAO TECH INTERNSHIP
📝 자료구조: Queue
-
리스트 사용
enqueue(추가)의 시간 복잡도는 O(1)이며, dequeue(삭제)는 O(N)이다. 추가의 경우는 큐의 맨 끝에서만 일어나지만, 큐의 첫번째 원소를 삭제할 경우에는 두번째 원소부터 맨 마지막 원소까지 모든 원소들의 위치를 왼쪽으로 한 칸씩 옮겨주어야하기 때문이다. -
collections.deque 사용
deque(데크)는 앞과 뒤 양방향에서 데이터를 처리할 수 있는 자료구조를 의미한다. 내부적으로 doubly 링크드 리스트로 구현되어 있기 때문에 O(1)으로 매우 빠르다. 단, deque의 중간에 삽입, 제거는 더 느리다.from collections import deque deq = deque() # Add element to the start deq.appendleft(10) # Add element to the end deq.append(0) # Pop element from the start deq.popleft() # Pop element from the end deq.pop()
👉 제출 코드
시간 초과를 고려하여 collections.deque를 사용한다.
최소 횟수를 찾기 위해서 큐의 원소 합이 큰 곳에서 작은 곳으로 이동시킨다.
from collections import deque
def solution(queue1, queue2):
answer = 0
q1 = deque(queue1)
q2 = deque(queue2)
sum1 = sum(q1)
sum2 = sum(q2)
for i in range(len(queue1) * 3):
if sum1 == sum2:
return i
elif sum1 > sum2:
num = q1.popleft()
q2.append(num)
sum1 -= num
sum2 += num
else: # sum1 < sum2
num = q2.popleft()
q1.append(num)
sum1 += num
sum2 -= num
return -1for문 안에서 sum을 다시 쓰지 않고 num을 빼고 더하는 산술연산으로 구현한다. ➡ sum 쓰면 시간 초과
for문의 범위(반복문 탈출 조건)
- queue1과 queue2를 바구려면 len(queue1) * 2만큼 횟수가 필요하다. ➡ fail test case1
- 반례:
다른 사람의 풀이 보기에서 참고)
"정확히 말하자면, len(queue1) 3 - 3입니다. 예를 들어, queue1 = [1]98 + [199, 1]이고, queue2 = [1]*100 이라면, 98+1+198=297번 옮겨야 합니다."
🙏 다른 사람의 풀이 보기
def solution(que1, que2):
queSum = (sum(que1) + sum(que2))
if queSum % 2:
return -1
target = queSum // 2
n = len(que1)
start = 0
end = n - 1
ans = 0
cur = sum(que1)
que3 = que1 + que2
while cur != target:
if cur < target:
end += 1
if end == n * 2:
return -1
cur += que3[end]
else:
cur -= que3[start]
start += 1
ans += 1
return ans- 둘로 나눌 수 없는 경우를 처리한다.
- 하나의 리스트로 합쳐서 본다.
- 한바퀴 돌았을 때 -1을 반한한다.
👀 참고 자료
's Coding Memory