오늘 푼 문제는 실버4 난이도, 백준 18258번 문제 "큐2"다.
블로그 쓰기를 1주일 동안 꾸준히 한다면 아마 네이버 블로그에 책 읽은 것들을 하나씩 올릴 것 같다.
(추억이니까 하고 싶은데 할 수 있을지는 모르겠다 ㅠㅠ)
내일 스키장을 가야 함에도 블로그 글을 쓰고 있는 인생이란...
반말과 존댓말이 섞여있는 이유가 궁금하다면 첫 번째 포스팅을 읽고 오길 바란다.
https://flydeepnight.tistory.com/14
BOJ 백준 9012번 문제 <괄호> python, 알고리즘 문제 푸는 방법
오늘부터 메타버스 아카데미 1기를 함께했던 (내가 가장 애정하는 AI반!) 사람들과 알고리즘 문제풀기 스터디를 하기로 하여서 내가 푸는 것마다 블로그에 포스팅을 할 예정이다. 블로그를 쓸 때
flydeepnight.tistory.com
문제:
https://www.acmicpc.net/problem/18258
18258번: 큐 2
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
문제에 대한 간단한 이해
- 큐를 구현하는 문제입니다. (큐는 자료구조 중 일부이고 따로 검색을 하길 바랍니다.)
입출력에 대한 이해
- 전체 명령어의 갯수가 주어지고 그 뒤 그 갯수만큼 명령이 주어집니다.
- 숫자값의 크기는 파이썬에선 큰 문제가 없고 C++이라 하더라도 int형으로 커버가 가능할 정도입니다.
문제에 대한 세부 이해
1. 주어진 것(입력값):
명령어 + 정수 X
명령어 뒤 정수가 필요한 경우에 띄어쓰기 후 정수 X를 적습니다.
2. 구하고자 하는 것(출력값)
push를 제외한 나머지 명령어들은 조건에 맞게 출력합니다.
3. 규칙
큐는 다음과 같은 특성이 있습니다.
- 가장 먼저 들어온 애가 가장 먼저 나간다 (FIFO: first in frist out)
- 나머지는 문제에 주어진 규칙 그대로입니다.
구현
어떤 것을 구현하라고 명시되어 있는 문제는 먼저 그것을 맞게 구현하는게 가장 정석입니다.
파이썬에서 리스트는 편리한 만큼 연산당 O(n)의 실행속도를 가지고 있습니다.(한번 연산당 크기만큼 걸림)
따라서 큐를 구현하라고 한다면 큐가 구현된 모듈이 있는지 확인해보는 것이 좋습니다.
[Python]파이썬, 왜 리스트대신 큐/ 데크 deque 를 쓸까?
Python deque deque 라는 것은 쉽게 말하자면 파이썬의 list 와 같이 요소들을 한 곳에 담아두는 배열이다. 파이썬에서 큐 queue는 First In First Out (FIFO) 의 방식으로 작동된다. 덱(데큐)는 큐는 큐이지만
codingpractices.tistory.com
시간초과를 경험해보시는 것도 경험입니다. 시간 초과가 났을 때 어디를 손봐야 할지 알 수 있기 때문입니다.
(그런데 필자는 이미 시간초과를 두번이나 당하고 모듈을 찾았습니다.)
dequeue를 이용하여 작업해보겠습니다.
필요한 작업 나열
- dequeue를 이용해 push pop 등의 기능 만들기
- 규칙에 맞게 출력될 수 있도록 if문과 print문 작성
- 입출력에 필요한 for문 작성
구현은 클래스를 이용할 수도 있지만 문제가 복잡해 보이지 않으니 큐의 기능을 만들겠습니다.
from collections import deque
N = int(input())
q = deque()
size = 0
back_num = -1
for i in range(N):
data = input().split()
if data[0] == "push":
q.append(data[1])
back_num = data[1]
size += 1
elif data[0] == "pop":
if size == 0:
print(-1)
continue
print(q.popleft())
size -= 1
elif data[0] == "size":
print(size)
elif data[0] == "empty":
if size == 0:
print(1)
else :
print(0)
elif data[0] == "front":
if size == 0:
print(-1)
continue
print(q[0])
else:
if size == 0:
print(-1)
continue
print(back_num)다음과 같이 작성하였더니 시간 초과가 또 뜹니다.
이렇게 줄일 대로 줄였을 경우에 입력 시간에서 많이 잡아먹는 경우가 많습니다.(C++도 마찬가지)
인터넷을 찾아보니 입력 받을 때 시간을 줄이는 방법이 있습니다.
import sys
from collections import deque
N = int(sys.stdin.readline())
q = deque()
size = 0
for i in range(N):
data = sys.stdin.readline().split()
if data[0] == "push":
q.append(data[1])
back_num = data[1]
size += 1
elif data[0] == "pop":
if size == 0:
print(-1)
continue
print(q.popleft())
size -= 1
elif data[0] == "size":
print(size)
elif data[0] == "empty":
if size == 0:
print(1)
else :
print(0)
elif data[0] == "front":
if size == 0:
print(-1)
continue
print(q[0])
else:
if size == 0:
print(-1)
continue
print(q[-1])sys.stdin.readline()을 input()대신 사용하여 시간을 단축시켰더니 성공하였습니다.
아래는 이 함수에 대해서 정리해놓은 블로그입니다.
[Python 문법] 파이썬 입력 받기(sys.stdin.readline)
파이썬으로 코딩 테스트를 준비한다면, 반드시 알아야 할 입력방식인 sys.stdin.readline()에 대한 정리 입니다.
velog.io
추가로 input보다 빠른 이유에 대해 정리되어 있는 블로그입니다.
=> 한줄 요약: 한 번에 읽어오고 그냥 뿌리므로 하나씩 버퍼에 저장하고 작업을 처리하는 input보다 빠릅니다.
https://hs-archive.tistory.com/35
input()과 sys.stdin.readline()의 차이
파이썬에서 input()과 sys.stdin.readline()의 차이에 대해 알아보자. 얻어갈 지식 input()과 sys.stdin.readline()의 차이 input() input()이 호출되면 인자로 주어진 문자를 화면에 출력하고 사용자의 입력을 기다
hs-archive.tistory.com
풀이부터 포스팅까지 1시간만에 끝내겠다고 마음먹었던 문제였는데 시간초과 3번을 겪고 1시간 40분이 걸려버렸다.
기록을 보니 예전에 C++로 풀었었는데 C++에서는 애초에 구현하는 게 일이었지 구현을 하면 시간 걱정은 안해도 됐었는데 여긴 이것저것 걱정되는게 많다는 걸 알게 됐다.
하지만 그래도 파이썬이 더 편한 건...사실 ㅎㅎ
'컴퓨터 공학 분야 별 지식 > 백준' 카테고리의 다른 글
| BOJ 백준 2559번 문제 <수열> python, 문제 해석 및 풀이 (0) | 2023.02.02 |
|---|---|
| BOJ 백준 2003번 문제 <수들의 합 2> python, 문제 해석 및 풀이 (0) | 2023.02.01 |
| BOJ 백준 1935번 문제 <후위 표기식> python, 문제 해석 및 풀이 (0) | 2023.01.19 |
| BOJ 백준 4949번 문제 <균형잡힌 세상> python, 문제 해석 및 풀이 (0) | 2023.01.18 |
| BOJ 백준 9012번 문제 <괄호> python, 알고리즘 문제 푸는 방법 (0) | 2023.01.16 |