문제
AC (https://www.acmicpc.net/problem/5430)
풀이
1. 초기 접근
- 문제조건 해석
- 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
- n <= 100,000 이므로, 최대 O(n log n) 안으로 풀어야한다.
- 함수 p 내 R,D 에 접근할 때마다, 리스트 연산의 시간복잡도가 O(1) 이어야 한다.
- 기본적으로 문제조건 및 해야할 일은 직관적이고 간단해보인다.
- 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
- 알고리즘
- 함수 p 가 RDD 로 주어지면, 어찌됐든 R, D, D 식으로 리스트 p를 한 번 탐색은 해야할 터,
기본 루프로 시간복잡도는 O(n) 이 들어간다. - 이제 루프 내 파이썬 리스트 연산을 O(1) 안에 끝내야 하는데, 이 때 파이썬 리스트 연산의 시간복잡도를
평소에 잘 알고있느냐가 기본이 된다. 모르고 있다면, 지금 구글링해서 찾아보자. D
의 경우, 첫 번째 원소를 pop 해야 하므로,deque
로 리스트를 구성하고,popleft()
를 사용함으로써 O(1) 만에 끝낼 수 있다.R
은 직관적으로reversed(list)
를 사용해야 함을 알 수 있다.
문제는, 이 연산은 시간복잡도가 O(n) 이라는 것이다. 즉 루프문 내 사용할 수 없다.
따라서 이 R 을 어떻게 처리할거냐가 이 문제의 관건인데, 다시 문제조건을 잘 보자.- 우리의 연산은
R
과D
만 주어진다. 즉 첫 번째 원소를 빼거나, 전체를 뒤집거나다.
만약 뒤집지 않고도, 뒤집은 효과를 볼 수 있을까? 이 상황에서 특별하게? - 일종의 flag 를 두자. 뒤집한 상태를 알 수 있도록.
만약 현재가 뒤집히지 않은 상태라면,D
가 주어졌을 때, 첫 번째 원소를 빼면 된다.
만약 현재가 뒤집힌 상태라면,D
가 주어졌을 때, 맨 끝의 원소를 빼면 된다. - 마지막으로 루프만 밖에서, 현재가 뒤집힌 상태라면,
reversed(list)
로 뒤집어주면 된다.D
가 왜 첫 번째 원소만 pop 하도록 주어졌는지, 이제야 그 의도가 보이지 않는가?
- 함수 p 가 RDD 로 주어지면, 어찌됐든 R, D, D 식으로 리스트 p를 한 번 탐색은 해야할 터,
- 코드
import sys
from collections import deque
t = int(input())
for _ in range(t):
p = list(sys.stdin.readline())
n = int(input())
x = sys.stdin.readline()
di = 1
try:
if n == 0:
x = []
else:
x = deque(list(map(int, x.strip()[1:-1].split(','))))
for i in p:
if i == 'R':
di *= -1
elif i == 'D':
if x:
if di == 1:
x.popleft()
else:
x.pop()
else:
raise ValueError
except ValueError:
print("error")
else:
if di == -1:
x = reversed(x)
print("[" + ",".join(list(map(str, x))) + "]")
'취업과 기본기 튼튼 > 코딩 테스트 노트' 카테고리의 다른 글
[프로그래머스] 야근 지수 (0) | 2019.09.21 |
---|---|
[프로그래머스] 가장 큰 수 (7) | 2019.07.12 |
[BOJ] 2493. 탑 (2) | 2019.04.18 |
[BOJ] 17135. 캐슬 디펜스 (0) | 2019.04.12 |
[BOJ] 14891. 톱니바퀴 (2) | 2019.04.11 |