[Algorithm][Python] 백준 5430 AC

01. 개요

새로운 언어 AC는 정수 배열에 특정 연산을 하기 위해 만들어진 언어

• R (뒤집기)
• D (첫 번째 수 버리기)
  • 배열이 비었을 때 D 함수를 실행하면 error 출력

함수 실행 명령어가 끝난 뒤의 결과를 출력하는 문제

100개 이하의 테스트 케이스
1번 이상 10만번 이하의 테스트 함수
배열의 수는 10만개 이하, 각 값은 100 이하

02. 풀이 방법

1 ) 연산마다 reverse 함수 사용

당연히 안된다.

• 처음 문제를 풀 때 시간 복잡도 계산을 잘못함
• 꼭! 주어진 테스트 케이스의 제한 조건을 잘 확인하고 시간 복잡도를 먼저 꼼꼼하게 계산해보자.

Test Case의 수가 100개고, 주어진 함수들이 모두 'R'이면서 그 개수가 10만개인 경우를 생각해보자. 심지어 주어진 정수 배열의 길이도 10만이라고 가정해보자.

• 10만 * 10만 * 100 => 1억

2 ) two pointer 사용

배열의 시작과 끝의 index를 별도 저장하여 각 연산마다 옮겨진 index를 가지고 있는 방식

주의할 점

• 출력 형태
  • Python의 기본 출력은 [1, 2, 3] 과 같이 숫자 간에 공백이 있음
• 뒤집힌 배열, 빈 배열 출력, pointer의 끝 값에 +1을 해주어야 정상 출력 (또는 pointer를 [0, n]으로 선언)

import sys

input = sys.stdin.readline

T = int(input().strip())

# TODO : start 와 end 가 바뀌었을 때, 'D' 명령어가 들어왔을 때의 동작이 다름 
# - example : start = 0 , end = 4 인 경우 'D' 명령어 입력시 start = 1 , end = 4
# - example : start = 4 , end = 0 인 경우 'D' 명령어 입력시 start = 3 , end = 0
def do_operation_by_pointer(order:str, pointer_pair:list, rest_num:int):
    
    if( 'R' == order) :
        pointer_pair[0], pointer_pair[1] = pointer_pair[1], pointer_pair[0]

    elif( 0 == rest_num):
        return pointer_pair, None
    
    elif('D' == order) :
        
        rest_num -= 1 
        s, e = pointer_pair
        add_val = 1 if s <= e else -1 
        pointer_pair[0] += add_val

    return pointer_pair, rest_num

for t in range(T):
    
    orders = list(input().strip()) # 1 < p <= 10만
    n = int(input().strip()) # sequences의 개수 
    sequences = input().strip()[1:-1]
    sequences = list(map(int,sequences.split(","))) if sequences != "" else []
    pointer = [0, n-1]
    rest_num = n

    for order in orders:
        
        # sequences = do_operation_by_reverse(order, sequences)
        pointer, rest_num = do_operation_by_pointer(order, pointer,rest_num)
        
        if(None == rest_num):
            print("error")
            break

    if( None != rest_num ):
        s,e = pointer

        if(0 == rest_num):
            print([])
        elif( s > e ):
            print(f'[{",".join(list(map(str,sequences[e:s+1][::-1])))}]')
        else:
            print(f'[{",".join(list(map(str,sequences[s:e+1])))}]')

3 ) Deque 이용

Deque의 pop 연산은 양방향으로 가능하다.
이 특성과 reverse 여부를 나타내는 flag를 함께 사용하여 문제 풀이

03. 아이디어

1 ) 'R'을 기준으로 자르기

Reference
jung0han님 풀이 참고

"RRDDRDR" 과 같이 명령어들이 입력되었을 때, "RR"을 공백으로 대체한다.

• 뒤집기 + 뒤집기는 원점..

"DDRDR"이 되고, 이를 "R" 기준으로 잘라서 각 원소의 길이만 남기면 [2,1,0]이 된다.

이 때, 홀수번째 index에 있는 값들의 합만큼 start_index에 더해지고, 짝수번째 index에 있는 값들의 합만큼 end_index에서 빠진다.

• 이 두 값의 합이 n보다 크면 error 출력

뒤집혀야 하는지 여부는 [2,1,0] 배열의 길이인 3에 1을 더하고 2로 나눈 나머지로 결정한다.