[백준/python]5430번 AC - string

풀이

함수에서 R이 등장할 때마다 뒤집고 D가 등장하면 삭제하게 된다면 최악의 경우 계속해서 뒤집기만 할 수 있기 때문에 이 방법은 아니라고 생각했다. 파이썬의 reverse 메서드의 시간 복잡도는 O(N)이다.

시간 효율에 중점을 두고 문제를 풀었다. D는 언제나 배열의 첫 번째 수를 버리므로 방향을 알려주는 변수를 선언하고 R이 등장하면 -1을 곱해서 지워야 하는 수를 모두 저장하고 한 번에 지우는 방식으로 풀었다.

1. way에 현재 방향을 1/-1로 저장해준다. 초기값은 1로 선언한다.
2. 함수 문자열을 탐색하며 R이면 way에 -1을 곱해 방향을 바꿔준다 / D가 등장하면 방향에 맞게 각각 f와 b에 지워야하는 숫자의 개수를 추가해준다.
3. 앞에서부터 f만큼 뒤에서부터 b만큼 배열을 slice해준다.
4. 마지막으로 저장된 방향이 -1이라면 reverse 메서드를 통해 배열을 뒤집는다.
5. 완성된 배열을 출력한다.

코드

T= int(input())

def AC():
    p = input()
    N = int(input())
    arr = input()
    arr=arr[1:-1].split(',')
    
    way = 1
    f, b = 0,0
    for i in range(len(p)):
        if p[i] == 'R' :
            way *= -1
        
        else:
          
            if way ==1:
                f+=1
            else :
                b-=1
                
    if (arr==[''] and f-b>0) or f-b > len(arr):
        print('error' )          
    else:
        
        if b==0:
            arr=arr[f:]
        else:
            arr=arr[f:b]
        
        
        if way==-1:
            arr.reverse()
        
        str='[' + ','.join(arr)+']'
        print(str)
    return

for _ in range(T):
    AC()