[BOJ/Python] 5430_AC

문제 출처:https://www.acmicpc.net/problem/5430

5430번: AC

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

예제 입력 1

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력 1

[2,1]
error
[1,2,3,5,8]
error

---

풀이

 

주어진 문자열에서 R이 나왔을 경우 뒤집고, D가 나올 경우 첫 번째 원소를 제거해야 하므로 deque를 이용하여 구현하였지만, 결론부터 말하자면 시간초과가 나왔다.

R의 경우 reverse()를 이용하여 뒤집고, D의 경우 popleft()를 이용하여 첫 번째 원소를 제거하였지만 reverse()의 시간복잡도가 O(N)이므로 주어진 문자열의 길이가 길어질수록 처리가 오래 걸린다고 생각하여 코드를 수정하여 다시 작성했다.

RR을 할 경우, 뒤집고 다시 뒤집으면 원래대로 돌아옴을 이용하였다.

 

우선 코드는 아래와 같다. 사실 아래의 코드 또한 시간초과가 나온 코드이다..

import sys
import collections
 
t = int(sys.stdin.readline())
 
for _ in range(t):
    deq = collections.deque()
    func = sys.stdin.readline()
    n = int(sys.stdin.readline())
    
    lst = list(sys.stdin.readline().strip().split(','))
    lst[0] = lst[0][1:]
    lst[-1] = lst[-1][:-1]
    lst = ' '.join(lst).split()
    deq.extend(lst)
 
    flag = True
    count = 0
    for i in func:
        if i=='R':
            count+=1
        elif i=='D':
            if count%2==1:
                deq.reverse()
                count = 0
 
            if len(deq)==0:
                flag = False
                break
            else:
                deq.popleft()
        else:
            if count%2==1:
                deq.reverse()
 
    if flag:
        print("[",end='')
        print(','.join(deq),end='')
        print("]")
    else:
        print("error")

• 여기서 reverse()의 횟수를 줄이기 위해 count라는 변수를 추가하였다.
• 주어진 문자열을 탐색하면서 'R'을 만났을 때, count변수의 값을 1 더해준다.
• 만약 'D'를 만나게 되면, 첫번째 원소를 제거해 줘 야하기 때문에 count변수가 홀수인지 짝수인지를 확인한다.
• 짝수라면 R이 짝수번 나온것이므로 뒤집을 필요가 없고, 홀수라면 뒤집은 뒤 첫 번째 원소를 제거하고, count를 0으로 초기화한다.
• 그리고 만약 제거할 원소가 없다면 반복문을 종료하고 error를 출력한다.
• 문자열의 경우 strip()을 하지 않았기 때문에 마지막에 '\n'을 탐색하게 되고, 이 경우 else부분이므로 최종적으로 count가 짝수인 경우 뒤집으며 문자열탐색을 마치고 출력한다.(하지 않았을 경우 RRR과 같은 문자열을 처리하지 않음)

하지만 여전히 문자열 탐색하는 과정에서 reverse()가 여러번 수행되기 때문에 시간초과가 나왔다.

그래서 어떻게 시간을 더 단축시킬 수 있을까 생각을 해봤고, pop()과 popleft()를 이용하면 reverse()를 사용하지 않고도 뒤집었다고 생각하여 연산을 수행할 수 있지 않을까? 하는 생각에 아래의 코드를 작성했다.

 

 

import sys
import collections
 
t = int(sys.stdin.readline())
 
for _ in range(t):
    deq = collections.deque()
    func = sys.stdin.readline().strip()
    n = int(sys.stdin.readline())
    
    lst = list(sys.stdin.readline().strip().split(','))
    lst[0] = lst[0][1:]
    lst[-1] = lst[-1][:-1]
    lst = ' '.join(lst).split()
    deq.extend(lst)
 
    flag = True
    count = 0
    for i in func:
        if i=='R':
            count+=1
        else:
            if len(deq)==0:
                flag = False
                break
 
            if count%2==1:
                deq.pop()           
            else:
                deq.popleft()
 
 
    if flag:
        print("[",end='')
        if count%2==1:
            deq.reverse()
            print(','.join(deq),end='')
        else:
            print(','.join(deq),end='')
        print("]")
    else:
        print("error")