6/30 코테 일지 (deque)

deque 사용법 

2164 카드2

deque는 doubly linked list로 구현되어 있어서 첫 번째 배열 pop시 array.pop(0)이 아닌 array.popleft()가 가능하며 연산속도가 굉장히 빠르다.

import sys 
from collections import deque

array= deque()
for i in range (int(sys.stdin.readline().rstrip())):
  array.append(i+1)



while len(array) != 1:
  array.popleft()
  array.append(array.popleft())
print(array[0])

 

테스트로 밑에 같이 array.pop(0)으로 해보았을때 시간초과가 뜨는 것을 확인하였다. 

import sys 
from collections import deque

array=  []
for i in range (int(sys.stdin.readline().rstrip())):
  array.append(i+1)



while len(array) != 1:
  array.pop(0)
  array.append(array.pop(0))
print(array[0])

 

그 외 문제들

1158 요세푸스 문제 

내 코드

import sys
from collections import deque

N,K = map(int,(sys.stdin.readline().rstrip().split(' ')))
array= []
for i in range(N):
  array.append(i+1)

answer =[]
new_K=0
while len(array) != 1:
  if len(array) > K:
    answer.append(array[K-1])
    temp_array = array[K:] + array[0:K-1]
    array = temp_array
  elif K % len(array) == 0:
    answer.append(array.pop())
  else :
    new_K = K % len(array) 
    if new_K == 1:
      answer.append(array[0])
      array.pop(0)
    else:
      answer.append(array[new_K-1])
      temp_array = array[new_K:] + array[0:new_K-1]
      array = temp_array
answer.append(array[0])

char = '<'
for i,x in enumerate(answer):
  char += str(answer[i])
  if i != len(answer)-1:
    char += ', '
char += '>'
print(char)

 

남의코드 

K를 곧이 곧대로 쓰지 말고 index가 어떻게 변하는 지에 대한 패턴을 잘 찾아서 풀자.

n, k = map(int,input().split())
queue = [i for i in range(1,n+1)]
ans = []

idx = k - 1
for i in range(len(queue)):
    if idx >= len(queue):
        idx %= len(queue)
        ans.append(str(queue.pop(idx)))
    else:
        ans.append(str(queue.pop(idx)))
    idx += (k-1)

print("<"+ ", ".join(ans) + ">")

 

3273 두 수의 합 

온갖 시도를 다 해보다 결국 블로 글을 참고해서 풀었다. 포인터 두 개를 사용해 비교하는 걸 잘 활용하자.

import sys
n = int(sys.stdin.readline().rstrip())
array = list(map(int,sys.stdin.readline().rstrip().split(' ')))
number = int(sys.stdin.readline().rstrip())

array.sort()
s= 0
e= n-1
count = 0
while s != e:
  if array[s] + array[e] < number:
    s += 1 
  elif array[s] + array[e] > number:
    e -= 1 
  else :
    count += 1
    s += 1 
print(count)

 

10845 큐

한 번에 성공

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
array= deque()

for _ in range(n):
  order = sys.stdin.readline().rstrip().split(' ')
  if len(order) == 2:
    order[1] = int(order[1])
  if order[0] == 'push':
    array.append(order[1])
  if order[0] == 'pop':
    if array: 
      print(array.popleft())
    else :
      print(-1)
  if order[0] == 'size':
    print(len(array))
  if order[0] == 'empty':
    if array:
      print(0)
    else :
      print(1)
  if order[0] == 'front':
    if array:
      print(array[0])
    else :
      print(-1)
  if order[0] == 'back':
    if array:
      print(array[-1])
    else :
      print(-1)