큐 2
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력
15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front예제 출력
1
2
2
0
1
2
-1
0
1
-1
0
3생각
이 문제에서 요구하는 것은 입력이 들어왔을때 if == 입력을 통해서 결과를 내보내면 되는 아주 쉬운 문제구나라고 생각을 하고 간단하게 풀어봄
초기코드
from collections import deque
# push X -> 정수 X를 큐에 넣는다
def push(x, queue):
queue.append(x)
# pop -> 정수 빼고 그 수 출력, 큐에 정수가 없으면 -1
def pop(queue):
if len(queue) == 0:
return -1
else:
return queue.popleft()
def size(queue):
return len(queue)
def empty(queue):
if len(queue) == 0:
return 1
return 0
def front(queue):
if len(queue) == 0:
return -1
return queue[0]
def back(queue):
if len(queue) == 0:
return -1
return queue[-1]
# 1 <= N <= 2000000
N = int(input())
queue = deque()
result = ""
for i in range(N):
inputs = list(map(str, input().split()))
if inputs[0] == "push":
push(inputs[1], queue)
elif inputs[0] == 'pop':
result += str(pop(queue)) +"\n"
elif inputs[0] == 'size':
result += str(size(queue))+"\n"
elif inputs[0] == 'empty':
result += str(empty(queue)) +"\n"
elif inputs[0] == 'front':
result += str(front(queue))+"\n"
else:
result += str(back(queue))+"\n"
print(result)
엥? 왜 시간초과..? 뭔가 오래 걸려보이는 것을 다 빼보자
result += str(값) 방식을 사용해서 문자열을 계속 연결하는 방식이 매우 비효율적이기 때문에
=> 파이썬에서 문자열은 불변객체이다(Immutable), 매번 += 연산을 할때마다 새로운 문자열 객체가 생성되고 이는 시간이 많이 소모되는 것일거다! 고로 리스트에 결과를 저장한후 .join()함수를 사용해서 해보자!
두번째 코드
from collections import deque
# push X -> 정수 X를 큐에 넣는다
def push(x, queue):
queue.append(x)
# pop -> 정수 빼고 그 수 출력, 큐에 정수가 없으면 -1
def pop(queue):
if len(queue) == 0:
return -1
else:
return queue.popleft()
def size(queue):
return len(queue)
def empty(queue):
if len(queue) == 0:
return 1
return 0
def front(queue):
if len(queue) == 0:
return -1
return queue[0]
def back(queue):
if len(queue) == 0:
return -1
return queue[-1]
# 1 <= N <= 2000000
N = int(input())
queue = deque()
result = []
for i in range(N):
inputs = list(map(str, input().split()))
if inputs[0] == "push":
push(inputs[1], queue)
elif inputs[0] == 'pop':
result.append(str(pop(queue)))
elif inputs[0] == 'size':
result.append(str(size(queue)))
elif inputs[0] == 'empty':
result.append(str(empty(queue)))
elif inputs[0] == 'front':
result.append(str(front(queue)))
else:
result.append(str(back(queue)))
print("\n".join(result))=> 이제는 되겠지..? => 시간초과....
또 시간초과네..? 이유가 뭐지..? 뭐가 문제지
len(queue)와 queue.count()의 차이는 무엇이지..?
- len(queue) => 시간복잡도 O(1)
- queue.count() => 시간복잡도 O(n)
옹 아니네 그러면 다른 이유가 무엇이 있을까?
내가 input()을 하는데 이게 시간이 좀 걸리는 것일까? 파이썬에서 빠르게 입력받는게 무엇이 있었지?
sys.stdin.readline().split()
input vs sys.stdin.readline()?
input() 내장 함수는 parameter로 prompt message를 받을 수 있다. 따라서 입력받기 전 prompt message를 출력해야 한다. 물론 prompt message가 없는 경우도 있지만, 이 경우도 약간의 부하로 작용할 수 있다. 하지만, sys.stdin.readline()은 prompt message를 인수로 받지 않는다.
또한, input() 내장 함수는 입력받은 값의 개행 문자를 삭제시켜서 리턴한다. 즉 입력받은 문자열에 rstrip() 함수를 적용시켜서 리턴한다. 반면에 sys.stdin.readline()은 개행 문자를 포함한 값을 리턴한다. 이 때문에 조금 귀찮은 점이 있기도 하다.
결론
결론적으로 input() 내장 함수는 sys.stdin.readline()과 비교해서 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴하기 때문에 느리다.
따라서 백준에서 Python으로 문제를 풀 때는 아래와 같이 sys.stdin.readline()을 활용해서 입력을 받는 것이 좋다.
[출처: https://buyandpray.tistory.com/7]
고로 기존의 코드를 sys.stdin.readline().split()으로 교체하여 코드를 작성하였다
import sys
from collections import deque
# push X -> 정수 X를 큐에 넣는다
def push(x, queue):
queue.append(x)
# pop -> 정수 빼고 그 수 출력, 큐에 정수가 없으면 -1
def pop(queue):
if len(queue) == 0:
return -1
else:
return queue.popleft()
def size(queue):
return len(queue)
def empty(queue):
if len(queue) == 0:
return 1
return 0
def front(queue):
if len(queue) == 0:
return -1
return queue[0]
def back(queue):
if len(queue) == 0:
return -1
return queue[-1]
# 1 <= N <= 2000000
N = int(input())
queue = deque()
result = []
for i in range(N):
inputs = sys.stdin.readline().split()
if inputs[0] == "push":
push(inputs[1], queue)
elif inputs[0] == 'pop':
result.append(str(pop(queue)))
elif inputs[0] == 'size':
result.append(str(size(queue)))
elif inputs[0] == 'empty':
result.append(str(empty(queue)))
elif inputs[0] == 'front':
result.append(str(front(queue)))
else:
result.append(str(back(queue)))
sys.stdout.write("\n".join(result))결론은 드디어 통과
느낀점
파이썬의 구조체나 이런 언어에 대한 방법도 잘 알고 있어야겠다는 생각이 들었다. 역시 오랜만에 풀었더니 실버도 어렵다.. 이제부터 꾸준히 풀면서 다시 알고리즘에 대한 감을 잡아봐야겠다
