5430번 AC(deque, cin동작) - ☆

#문제링크 : https://www.acmicpc.net/problem/5430

함수와 배열을 "[1,2,3,4]"의 형태로 입력받고 해당 함수대로 동작한 후의 결과를 출력한다. R은 뒤집기, D는 맨 앞 삭제, 앞의 요소를 삭제하기 용이한 deque으로 자료구조를 생각하고 구현했다. 반례를 잡지 못해서 여러번 틀렸다가, 반례를 찾고 수정했으나, 시간초과가 됐다.

※주의사항

1. 입력형태가 복잡하지만, 형태를 잘보면, "기호-숫자-기호-숫자...-숫자-기호"다. 즉, char형 변수로 기호들을 받아내고, int형 변수로 숫자를 받으면 deque에 담을 수 있다.

2. 입력 배열의 크기가 0인경우 "[]"만 입력받아야 하므로 따로 구분지어서 넣어줘야 한다.(반례)

1. Code

<2nd try>

rev함수에서 직접 덱의 요소들을 뒤집는 과정에서 시간이 많이 소요된다. 배열의 최대 길이가 10만, 함수 최대 길이가 10만, T의 최대가 100이므로 함수의 'R','D'만 판별하는 데에만 대충 1000만번, 그 내부에서 rev 함수를 돌리면 1억번을 훌쩍 넘는다. 따라서 직접 뒤집으면 안되고 출력방향만 반대로 해주면서 각각 함수 'R'의 입력 횟수에 따라 front에서 pop할지, back에서 pop할지 결정하고, 출력도 거꾸로할지 그대로 할지 결정하면 된다.

※주의사항

1. 'R'의 입력횟수에 따라 pop의 방향과 출력방향을 다르게 해야한다.

2. Code