[백준] 5430번 AC

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초이다.
1초에 해당하는 연산은 대충 1억정도인데 이 문제의 입력 배열의 최대 크기는 10만이고 명령어의 최대 길이 역시 10만이다. 즉, 10만개의 명령어가 모두 R명령어라서 reverse연산을할 때 배열의 크기가 10만인 경우에는
100000 * 100000 는 100억이기 때문에 1초 안에 수행할 수 없게된다.

그래서 R 연산에 대해서는 flag를 세워서 지금 배열이 뒤집어져있는지 아닌지만 판단하고
deque자료구조를 이용하여 flag가 1인 경우에는 pop flag가 0인 경우에는 popleft로 D연산을 수행하고 마지막 결과 출력하는 부분에서 flag를 체크해서 1인 경우에는 reverse하는 방법으로 구현하였다.

    #N이 1보다 큰 경우는 [] 슬라이싱으로 제거하는 작업 수행
    if N != 0 :
        numbers = input()
        numbers = deque(map(int,numbers[1:len(numbers)-1].split(',')))
    #N이 0인 경우에는 슬라이싱하는 순간 내용이 없기 때문에 바로 deque에 []입력
    else :
        dump = input()
        numbers = deque()

먼저 입력에서 [1,2,3,4]와 같이 괄호와 ,과 같이 들어오기 때문에 리스트의 1번부터 n-1번까지를 ,로 구분하여 다시 deque에 저장하는데 N이 0인 경우에는 바로 빈 deque를 생성하였다.

 

    flag = 0
    print_flag = 1
    for cmd in cmds :
        #직접 reverse를 수행하지 않고 표시만 변경
        if cmd == 'R' :
            flag = (flag + 1)%2
        elif cmd == 'D' :
            if len(numbers) == 0 :
                print('error')
                print_flag = 0
                break
            if flag == 0 :
                numbers.popleft()
            else:
                numbers.pop()

reverse를 직접 수행하지 않고 표시만 하기위한 flag와 error를 출력한 경우에는 deque의 내용을 출력하지 않기 위해서print_flag를 지정하였다.
명령을 1개씩 받으면서 R인 경우에는 flag를 변경하고 D인 경우네는 flag를 체크하여 reverse 상태면 pop() 그렇지 않다면 popleft()를 해서 데이터를 제거하였다.

    if flag == 0 and print_flag == 1:
        str1 = ','.join(map(str,numbers))
        print('['+str1+']')
    elif flag == 1 and print_flag == 1:
        numbers.reverse()
        str1 = ','.join(map(str,numbers))
        print('['+str1+']')

마지막에 flag를 체크해서 reverse 연산을 수행하고 처음 입력받은 형식으로 괄호와 ,를 추가하여 출력하면된다.
error인 경우에는 빈 리스트를 출력하지 않고 error가 아닌 경우에는 빈 리스트여도 출력해야하기 때문에
print_flag를 추가적으로 확인하였다.

 

 

 

전체 코드

import sys
from collections import deque

T = int(input())

for i in range(T):
    cmds = list(sys.stdin.readline().strip())
    N = int(sys.stdin.readline().strip())

    #N이 1보다 큰 경우는 [] 슬라이싱으로 제거하는 작업 수행
    if N != 0 :
        numbers = input()
        numbers = deque(map(int,numbers[1:len(numbers)-1].split(',')))
    #N이 0인 경우에는 슬라이싱하는 순간 내용이 없기 때문에 바로 deque에 []입력
    else :
        dump = input()
        numbers = deque()

    flag = 0
    print_flag = 1
    for cmd in cmds :
        #직접 reverse를 수행하지 않고 표시만 변경
        if cmd == 'R' :
            flag = (flag + 1)%2
        elif cmd == 'D' :
            if len(numbers) == 0 :
                print('error')
                print_flag = 0
                break
            if flag == 0 :
                numbers.popleft()
            else:
                numbers.pop()

    if flag == 0 and print_flag == 1:
        str1 = ','.join(map(str,numbers))
        print('['+str1+']')
    elif flag == 1 and print_flag == 1:
        numbers.reverse()
        str1 = ','.join(map(str,numbers))
        print('['+str1+']')