5430: AC

문제 해석

단계별로 풀어보기의 큐, 덱 파트에서 가장 어려운 문제이다.

문제를 요약하면 입력으로 R이 들어오면 정수 배열을 뒤집어야하고, D가 들어오면 배열의 첫 번째를 버리는 작업을 해야한다. D가 들어올 때 마다 하는 동작은 먼저 들어온 값을 먼저 내보내는 큐에서의 pop()과 동작이 같다.

이렇게 함수를 실행하고 남은 결과를 출력하는 문제이다.

시행착오

이 문제는 처음 봤을 때 골드 5티어 라고 하기에는 너무 간단해보였다.

떠오른 생각대로 알고리즘을 구현하고 제출했더니 시간 초과를 받았다.

단순히 배열을 사용하거나 python의 deque 라이브러리를 사용한다고 하더라도 R을 문제에서 유도한 방식대로 처리하지 않는다면 시간 초과를 받을 수 밖에 없을 것이다.

 

그 이유는 Reverse를 수행하면 원소 수만큼의 시간이 소요될텐데

입력 조건에 따르면 최대 10만개의 원소가 들어올 수 있고 R도 최대 10만개가 들어올 수 있다.

그러면 10만개의 원소를 10만번 Reverse를 수행한다면 어떻게 될까..?

연산 횟수만 100억번 이라는 수치가 나온다.

통상 C언어를 기준으로 연산 횟수가 10억을 넘어가면 1초 이상이 소요된다고 하는데, 이 방법은 시간 초과를 부를 수 밖에 없는 연산 횟수가 나온다.

이 때문에 진짜로 Reverse를 수행하면 안된다는 것을 짐작할 수 있었다.

사용한 풀이방법

그러면 어떻게 해야할까..?

함수는 뒤집거나 지우는 동작 밖에는 없다.

그러면 양방향 큐를 의미하는 deque를 생각해봤을 때 R 없이 D를 수행하면 첫 번째 원소가 삭제되는데

R를 한 번 하고 D를 하면 맨 마지막 원소가 삭제된다.

그런데 R을 두 번 하면 R을 안한 것과 같은 효과가 있다. (뒤집고 다시 뒤집었으니까..)

즉 RR을 하고 D를 한 것과 바로 D를 한 것이 같고, R을 한 번 하고 D를 하는 것과 RRR을 하고 D를 하는 것이 같다.

이것은 R을 몇 번 했냐에 달려있다.

R을 짝수 번만큼 했다면 정수 배열의 순서는 그대로가 되어야 하고, R을 홀수번 만큼 했다면 정수 배열은 뒤집힌 상태가 되어야 한다.

따라서 배열의 순서가 그대로라면 왼쪽의 원소를 삭제하고, 배열의 순서가 뒤집혀있다면 오른쪽의 원소를 삭제하면 된다.

 

이러한 알고리즘으로 코드를 구현했을 때 정답 판정을 받을 수 있었다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

from collections import deque   t = int(input())   for _ in range(t):   p = input()   n = int(input())   array = eval(input())   result = 0     queue = deque(array)     reverse_count = 0   result = ''   for order in p:     if order == "R":       reverse_count += 1     elif order == "D":       if len(queue) > 0:         if reverse_count % 2 == 0:           queue.popleft()         else:           queue.pop()       else:         result = 'error'     if result != 'error':     s = '['       if reverse_count % 2 == 1:       queue.reverse()            for rs in queue:       s += str(rs) + ','       if len(queue) == 0:       s += ']'     else:       s = s[:-1] + ']'       result = s     print(result)   Colored by Color Scripter

cs

 

참고

이 문제는 제출 대비 정답 비율이 낮은 문제인 만큼 많이 실수하는 부분에 대해서 정리를 해놓은 고마운 분이 있다!

나도 문제를 풀 때 많은 도움을 받았던 글이다.

풀다가 막힌다면 정답 코드 보다 먼저 보기를 권한다.

링크: https://www.acmicpc.net/board/view/25456