[백준] 5430번
AC
PYTHON
5430번 AC
시간 제한으로 인해서 은근 난이도가 높은 문제이다.
예제 출력을 얻어내는 알고리즘을 구현하는 것은 매우 간단하다. 문제에서 주어진 명령을 그대로 수행하면 되기 때문이다.
따라서 문제에 대해 따로 해석할 것은 존재하지 않는다.
하지만 직전에 말한 것 처럼 시간 제한이 계속 발목을 잡는다.
일단 시간 제한으로 실패했던 코드부터 살펴보자.
시간 초과 코드
시간 초과에 걸렸기 때문에 통과하지 못했지만 실패한 코드라고 생각하지 않는다. 알고리즘 적으로 문제가 존재하는 코드는 아니기 때문이다.
위와 같은 이유로 시간 초과를 더욱 더 해결하기 힘들었다.
코드를 다시 읽고 또 읽어도 리스트를 뒤집는 경우를 제외하면 더 간단하게 만들기 어렵다고 생각했다.
따라서 문제에서 주어진 'R' 과 'D' 연산을 조금 더 구체적으로 생각했다.
소스 코드
리스트를 뒤집는 연산이 만약 시간을 많이 쓴다면 뒤집는 연산을 효율적으로 하거나, 뒤집지 않으면 된다.
뒤집는 연산을 하지 않는 방법을 고안해보면 'D' 연산에서 힌트를 얻을 수 있다.
'D' 연산은 가장 앞쪽의 원소를 삭제하는 것이라고 나와있지만 만약 뒤집기 연산이 한 번 즉, 홀수번 이루어지면 가장 뒤쪽의 원소를 삭제하는 것과 동일하다.
또한 뒤집기 연산은 짝수번 이루어지면 사실 이루어지지 않은 것과 동일하다.
그래서 'r' 변수에 'R' 연산이 입력된 횟수를 저장하여 처리했다.
문자열에 대한 처리는 각 언어별로 다르겠지만 Python의 슬라이싱 기법을 이용했다.
Whiplash We Flash