문제 출처 : https://www.acmicpc.net/problem/5430
사고과정
심플했다. R과 D라는 두가지 기능밖에 없어 뒤집거나(1) 요소를 제거(2)만 하면 됐다.
입력받은 문자 배열에서 숫자를 제외한 다른 기호들을 제거하기 위해 "파이썬 알고리즘 인터뷰"에서 봤다시피 빠른 효율을 자랑하는 정규식을 이용하여 처리했다. 처음에는 문자열에 관한 문제여서 생각없이 R을 순수하게 기능 구현했다. arr=arr[::-1] 이렇게 하면 당연히 요소들을 뒤집고 하는 데 시간이 오래 걸리게 된다. ( 짧은 문자열과 같은 경우 상관없지만 이 문제처럼 개수가 100,000 개쯤 되는 문제들은 시간을 항상 고려해야 한다. )
그래서 시간을 단축시키기 위해 수정해야 했고 R이라는 기능을 구현함에 있어 직접 뒤집을 필요없이 배열여부에 따라 앞뒤 문자의 제거만 가능케 하면 될것 같아 DEQUE를 이용하기로 했다. 결과는 성공적!
import sys
import re
from collections import deque
T = int(sys.stdin.readline().rstrip("\n"))
def AC(function,n) :
global nums #함수 내부 변경을 통해 밖에서도 변경 적용
reverse=1
for f in function :
if f == "R":
reverse = 1 if reverse==-1 else -1
continue
elif f == "D" :
if not nums:
return False
if reverse==1 :
nums.popleft()
else: #reverse==-1
nums.pop()
if reverse==-1:
nums=list(nums)[::-1]
return True
for _ in range(T) :
function = sys.stdin.readline().rstrip("\n")
n = int(sys.stdin.readline().rstrip("\n"))
nums = deque(list(re.sub('[^0-9]',' ',sys.stdin.readline().rstrip("\n")).split()))
if AC(function,n) :
print("["+",".join(list(nums))+"]")
else :
print("error")더 효율적인 방식의 추구는 항상 옳다 그래서 빠르게 돌아가는 다른 사람의 코드를 참고해보자.
nums = deque(list(re.sub('[^0-9]',' ',sys.stdin.readline().rstrip("\n")).split()))정규표현식을 다르게 작성
nums = deque(sys.stdin.readline().rstrip("\n")[1:-1].split(","))이때! 재밋는 오류 발생
위의 코드는 좌측과 같이 제대로 작동하는 반면 아래 코드는 우측과 같이 deque에 뭔가 남아있는다.
슬라이싱을 사용해서인지 인덱스상 아무것도 가르키지 않는다 해도 문자열이란 객체를 생성하는 듯하다.
또한
list나 deque에 빈 문자열에 대해 pop()을 해도 오류가 발생하지 않는다? 빈 문자열 또한 pop이 가능!!! pop()하고 나면 empty 상태.
암튼 이부분에 대한 건 머릿속에 참고하도록 하고( split의 응용도! ) 위의 방식으로 정규표현식을 슬라이싱해서 작성하면 시간이 두 배정도 단축된다.
외부 변수의 값을 변경하고 싶을 때는 global 또는 반환값을 이용하여 변경 내용을 전달한다.
