💡 백준 5430:
덱 기본 구조 활용
🌱 코드 in Python
알고리즘: Deque
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
cmd = input().rstrip()
n = int(input())
n_li = input().rstrip()[1:-1].split(',') # 첫,마지막 대괄호 제외 및 쉼표 생략 후 list화
rev = 0 # reverse 횟수 체크
flag = 0 # error 체크
for a in cmd:
if a == 'R':
rev += 1
elif a == 'D':
if not n_li or n == 0:
print("error")
flag = 1
break
else:
if rev % 2 == 0: # reverse횟수가 짝수번일 때는 0번일때와 같으므로
n_li.pop(0) # 앞에서 pop
else: # 홀수일 경우 reverse를 해야 하므로
n_li.pop()
if not flag and rev % 2 == 0: # 에러가 없을 경우에만 출력 진행
print(n_li)
print("[" + ",".join(n_li) + "]")
elif not flag and rev % 2 != 0:
n_li.reverse() # reverse가 홀수면 reverse 1회 진행
print("[" + ",".join(n_li) + "]")이번 문제는 R연산에 대한 처리가 시간초과와 아주 밀접한 연관을 가지고 있는 문제였다
다시 말해 그것이 함정이었다는 말!
나도 처음에는 R이 나오면 무조건 reverse를 수행했었다
그러다가 입력값 처리에 대한 방법을 찾으러 간 블로그에서 우연히 그 함정을 알게되어..
다행히 피할 수 있었다.. ㅎㅎ
입력값에 대한 처리는 쉼표 지우는 건 쉽지만 대괄호 지우는 방법을 몰라
n_li.replace('(', "")와 같이 처리했다가 너무 지저분해 보여서 다른 방법이 없나 하고 찾으러 간 거 였다
입력값에 대해서도 [1:-1]와 같이 슬라이싱을 할 수 있다니... 대다네!!!😲
아무튼, split과 slicing을 잘 접목시켜 입력값을 int 배열로 변경하고
배열을 순회하며 명령어를 처리해주면 된다
다만 여기서 조심해야 할 것은, 위에서 말한바와 같이 reverse를 무턱대고 다 실행해주면 시간초과가 뜬다는 것이다
따라서 reverse 횟수를 기록해두었다가 reverse 횟수가 홀수이면 마지막에 그 한 번만 실행하여 런타임을 줄여야 한다
또한, D의 경우에 중간에 만약 reverse가 된 상태에서 D가 되었다면 앞이 아닌 뒤에서 빠졌을 것이므로 그를 반드시 고려해주어야 한다
아 그리고 이 문제는 파이썬의 deque 모듈을 import 해서 풀어야 속도가 훨 빠른 것 같다
아마도 queue는 배열, deque는 linked list로 구현이 되어 있는듯,,?
그래서 queue가 앞쪽 pop을 할 시 배열 인덱싱이 O(N)만큼 걸려서 시간이 오래걸리는 것 같다
덱일 경우에는 앞 뒤 빼는게 자유롭겠지만 말이다..
아님 망구...
🧠 기억하자
-
슬라이싱
- 슬라이싱을 잘 활용하자!
-
다시 한 번, 시간초과에 유념하자!
