2022. 3. 6. 00:46ㆍAlgorithm
[deque (python)]
백준 #10866 덱:
계속 시간초과가 나옴 ㅠ 제한시간 0.5초
ord=input()
if "push_front" in ord:
num_index=ord.find(' ')
num=int(ord[num_index+1:])
queue.appendleft(num)
처음엔 input()을 split()할 생각을 못함.
왜? push_front, push_back 외에는 그냥 한 덩어리(?)로 끝나니까 split() 할게 없다고 생각해서..
근데 그냥 상관없는 거였다.
아무튼 그래서 split()하고 좀 더 간결하게 만들었는데:
ord=input().split()
if "push_front" in ord:
queue.appendleft(ord[1])
역시 시간초과.
결국 구글링해서 찾아보니까 input()으로 받는게 아니라 sys.stdin.readline() 으로 받아와야 한다..
시간이 더 빠름.
최종 답:
#10866 덱
from collections import deque
import sys
n=int(sys.stdin.readline())
queue=deque()
for _ in range(n):
ord=list(sys.stdin.readline().split())
if "push_back" in ord:
queue.append(ord[1])
if "push_front" in ord:
queue.appendleft(ord[1])
if ord[0]=="front":
if len(queue)>0:
print(queue[0])
else:
print(-1)
if ord[0]=="back":
if len(queue)>0:
print(queue[-1])
else:
print(-1)
if ord[0]=="size":
print(len(queue))
if ord[0]=="empty":
if len(queue)>0:
print(0)
else: print(1)
if ord[0]=="pop_front":
if len(queue)>0:
a=queue.popleft()
print(a)
else:
print(-1)
if ord[0]=="pop_back":
if len(queue)>0:
a=queue.pop()
print(a)
else:
print(-1)
* deque로 큐를 만들 때 큐에서 앞, 뒤가 각각 왼쪽인지 오른쪽인지 헷갈렸는데
정리하자면,
큐의 앞: 덱의 왼쪽
큐의 뒤: 덱의 오른쪽
따라서 큐의 앞에 원소를 넣는다 하면 deque.appendleft(*) 를 쓰고
큐의 뒤에 넣는다 하면 deque.append(*)를 쓰면 된다.
* 참고로 deque 라이브러리는 큐를 사용할 때만 유용하고 스택이나 다른 자료구조를 구현할 때는 그냥 list를 쓰면 된다고 한다.
큐는 앞, 뒤 모두 접근이 가능해야하는데 deque가 popleft(), appendleft() 메소드가 있기 때문에 리스트를 다 훑지 않고도 바로 접근이 가능하기 때문에 시간이 더 빠르기 때문.
[dfs,bfs (또) 복습]
백준 #2606 바이러스
- 여태 풀었던 문제들 중에선 풀기 그나마 쉬운 편이었다..
- 근데 아직 언제 dfs를 쓰고 언제 bfs를 쓰는지 감이 크게 오지는 않는다.. 일단 bfs는 최단거리에 쓰는 건 알겠는데,, 다시 복습해야겠다
- 이 문제에선 dfs일 것 같아서(?) dfs로 우선 풀어봤고, bfs도 풀어봤는데 시간은 dfs로 푸는 게 더 빠르다.
DFS:
#2606
cnt_computers=int(input())
connected=int(input())
graph=[[] for i in range(cnt_computers+1)] #인덱스 숫자 맞춰주기 위해 +1
visited=[False]*(cnt_computers+1)
for _ in range(connected):
a,b=map(int,input().split())
graph[a].append(b)
graph[b].append(a)
def dfs(graph, v, visited):
visited[v]=True
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph,1,visited)
a=visited.count(True)-1 #1번 컴터 제외
print(a)
BFS:
#2606
cnt_computers=int(input())
connected=int(input())
graph=[[] for i in range(cnt_computers+1)] #인덱스 숫자 맞춰주기 위해 +1
visited=[False]*(cnt_computers+1)
for _ in range(connected):
a,b=map(int,input().split())
graph[a].append(b)
graph[b].append(a)
from collections import deque
def bfs(graph,start,visited):
dq=deque([start])
visited[start]=True
while dq: #덱이 빌 때까지
v = dq.popleft()
for i in graph[v]:
if not visited[i]:
dq.append(i)
visited[i]=True
bfs(graph,1,visited)
a=visited.count(True)-1
print(a)
'Algorithm' 카테고리의 다른 글
[BOJ][그래프] 백준 1012번 파이썬: 유기농 배추 (4) | 2022.03.14 |
---|---|
[BOJ][DFS] 백준 2667번 파이썬: 단지번호붙이기 --얕은복사와 깊은복사, dfs (5) | 2022.03.11 |
[백준] DFS, BFS (단지번호붙이기) (0) | 2022.03.04 |
[백준] BFS 복습(최단 경로 미로 탈출) (0) | 2022.03.04 |
DFS 와 BFS 개념 (0) | 2022.02.26 |