[백준][파이썬] 5430 AC

# 문제 링크

https://www.acmicpc.net/problem/5430

(문제 이름이 에이씨... 풉)

 

# 문제

선영이는 주말에 할 일이 없어서 새로운 언어 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를 출력한다.

 

# 예제

예제입력	예제출력
4 RDD 4 [1,2,3,4] DD 1 [42] RRD 6 [1,1,2,3,5,8] D 0 []	[2,1] error [1,2,3,5,8] error

 

---

# 문제 풀이

https://github.com/taerimiiii/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/5430.%E2%80%85AC

Algorithm/백준/Gold/5430. AC at main · taerimiiii/Algorithm

 

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t) :

    # 입력 처리
    p = input().strip()
    n = int(input())
    arr = list(input().split(','))

    # xi 배열에서 대괄호 삭제
    if n == 0 :
        arr = []
    elif n == 1 :
        arr[0] = arr[0][1:-2]
    else :
        arr[0] = arr[0][1::]
        arr[-1] = arr[-1][0:-2]
    
    # RD 함수 연산
    p_len = len(p)
    direct = 0      # 짝수 앞, 홀수 뒤 부터
    success = True  # 성공여부
    for i in range(p_len) :
        if p[i] == 'R' : # R(뒤집기) 이면
            direct += 1  # 방향 갱신
        else :                  # D(삭제) 이면
            if len(arr) == 0 :  # 배열 원소가 없으면
                success = False # 실패 처리
                break
            if direct % 2 :     # 역방향이면
                arr.pop()       # 맨 뒤 pop
            else :              # 정방향이면
                arr.pop(0)      # 맨 앞 pop
    
    # 출력 처리
    if success :
        arr_len = len(arr)
        if direct % 2 :
            print('[', end='')
            for i in range(arr_len-1, -1, -1) :
                print(arr[i], end='')
                if i != 0 :
                    print(',', end='')
            print(']')
        else :
            print('[', end='')
            for i in range(arr_len) :
                print(arr[i], end='')
                if i != arr_len - 1 :
                    print(',', end='')
            print(']')
    else :
        print("error")

 

RD 함수 연산 코드짜는 것 보다 대괄호 삭제하고 출력 처리하는게 더 힘들었다. 골드5 문제였는데 실버에 가야하는 문제 아닐까,, 그런 생각이 들었다. 시간복잡도 계산을 조금 생각해야 해서 골드에 있는건가..? 싶기도 했다.

 

R은 배열을 뒤집는 연산이지만 나올 때 마다 배열을 갈아 없으면 *O(N)으로 시간이 뻥튀기 되므로, direct 이라는 초기값이 0인 방향을 담는 변수를 만들어서 R이 나올 때 마다 1씩 더해주었다. 그리고 맨 마지막에 출력 할 때 direct가 홀수면 뒤에서 부터, 짝수면 앞에서 부터 출력했다.

 

D는 삭제 연산으로 역방향 상태일 때 삭제는 pop 함수를 사용하면 시간복잡도가 O(1) 이라 괜찮았지만, 정방향 상태일 때는 O(n)이라 고민이 되었다. 하지만 시간제한은 1초이고 t, n, p 범위 계산을 때려보면 얼추 통과 될 것 같은데?? 싶었다. 그래서 그냥 질렀는데 통과되었다 ㅎㅎ.

 

만약 시간초과가 발생한다면 xi 배열의 시작 인덱스를 가리키는 변수를 추가해서, 정방향 상태일 때 D가 나온다면 이 변수 값을 1씩 증가시켜 줄 계획이었다.