https://www.acmicpc.net/problem/5430
해당 문제에서 틀렸던 점은 시간복잡도가 주 원인 이였다.
1. R 명령어를 받을 때 모든 배열을 뒤집어 주면 O(N)의 시간 복잡도가 발생하므로 시간 초과가 발생하게 된다.
이를 해결하려면 R 명령을 받을때마다 배열을 뒤집어 주지 않고 현재 상태가 정상적인 상태인지 뒤집어진 상태인지만 표시하면 된다. 뒤집어진 상태에서 D 명령을 받으면 뒤에서 빼주고 정상적인 상태라면 앞에서 빼주면 된다. (
2. list 의 경우 앞에 있는 인덱스의 값을 제거할 경우 이 또한 시간 복잡도가 많이 발생하므로 큐로 해주어야 한다.
3. 출력 또한 배열로 되어있지만 배열로 출력을 하면 오류가 난다. str형식으로 배열 형태를 갖추어서 출력해주어야 한다.
import collections
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
result = True
number = collections.deque()
stack = list()
command = list(input().rstrip())
n = int(input().rstrip())
arr = input().rstrip()
if n:
arr = arr[1:-1].split(',')
for i in arr:
number.append(int(i))
reverse = False
for com in command:
# R 명령어를 받을떄마다 모든 배열을 뒤집어주면 많은 O(N) 의 복잡도가 발생하므로 현재 상태가 뒤집어져 있는 상태인지 아닌지만 바꿔준다
if com == 'R':
if reverse:
reverse = False
else:
reverse = True
# 배열이 뒤집어져 있을경우 맨 뒤에서 빼주고, 그대로일 경우 앞에서 빼준다.
elif com == 'D':
if len(number) == 0:
result = False
break
elif reverse:
number.pop()
else:
number.popleft()
if result:
if reverse:
# deque 의 경우 reverse 함수를 사용할 경우 내림차순 정렬이 아닌 순서만 뒤집어 준다.
number.reverse()
# 출력은 리스트가 아닌 str 형식으로 해야함.
print('[' + ','.join(map(str, number)) + ']')
else:
print('error')
'코딩테스트' 카테고리의 다른 글
[python] 백준 1927 : 최소 힙 (실버 2) (0) | 2024.07.12 |
---|---|
[python] 백준 1764 번 : 듣보잡 (실버 4) (0) | 2024.07.12 |
[python] 백준 1620번 : 나는야 포켓몬 마스터 이다솜 (실버 2) (0) | 2024.07.11 |
[python] 백준 11723 : 집합 (실버 5) (0) | 2024.07.11 |
[python] 백준 1012번 : 유기농 배추 (실버2) (0) | 2024.07.10 |