왜 틀렸을까?

• R 이 매번 나올 때마다 뒤집기에는 n이 10만이다.
  즉 10만 * 10만 이므로 나는 R 이 짝수면 그대로 홀수면 뒤집는 식으로 했는데,,,, 16퍼센트에서 틀린다.

반론!

RDRDRDRDRDRD 이렇게 되면 ㅋㅋ 어떻게 될지...
그렇다는 것은 10만 중에서 5만번의 Reverse가 발생한다는 것이고,
R의 비용 10만 * 5 만의 시간복잡도가 발생한다.

-> 즉 5000000000 : 50억의 시간복잡도 발생한다.

• => 다른 문제 해결전략을 제시해야 한다.

덱으로 풀 수 있따....

• 대박 사건!

• 일단은 reverse를 대체할 수 있는 것이 뭐가있을까???? 생각을 해야 한다...
  : R을 한번 한 다음에 D가 온다고 한다면 1234 에서는
  A방법) 진짜 뒤집기
  : 4321 그리고 4가 pop하게 된다.
  그런데 이거를 곧이 곧대로 뒤집지 말고
  B방법) R이 홀수면 뒤에 있는거 pop하기!
  1234에서 생각해보면, 그냥 뒤에 있는거를 pop 하면 된다.
  이 때는 123이 된다.

• 다시 R과 D가 발생했다고 하자. 그러면 곧이 곧대로 하게 되면,
  A방법은 뒤집기
  : 321 에서 123이 된다. 그리고 23이 된다.

B방법은 R이 짝수번이니까. 이번에는 남아있는 123에서 앞에거를 빼면 되지 않을까? -> 23이 나온다.

결론

: 나는 단순히 R 을 그냥 짝수번 나오면 안하고, 홀수번 나오면 뒤집어야 겠다. 이렇게 해도 시간복잡도 ㄱㅊ 고고씽 했지만,

• 반론을 가지고, 즉 최악의 반례를 생각해보니까. 이렇게 하면 안된다. 는 생각을 했고, 다른 방법을 생각해야 한다.

• 일단 내가 생각한 R이 짝수번인가? 홀수번을 가지고 뭔가 좀 다르게 할 수 있지 않을까? 를 생각해야 했다. '

-> 솔직히 단번에 덱 문제 구나! 라는 것을 파악하기에는 어렵다.

핵심.

• 하지만, reverse는 절대 사용하지 않으면서 R다음에 D가 오면 뒤에 있는거를 pop, 그냥 D가 오면 앞에는 pop 하면 되네?
  -> 앗!! 덱으로 접근해도 되겠구나! 를 생각할 수 있다.

• 즉, 해결전략하는데 시간을 많이 소요하는 것이 중요했따.