[BOJ/Python] 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를 출력한다.

< Code >

첫 번째 코드 - 시간 초과

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for tc in range(T):
    p = input().rstrip()
    n = int(input())
    nums = deque(input().rstrip()[1:-1].split(','))

    if n == 0:
        nums = deque()
    temp = 0
    for i in p:
        if i == 'R':
            nums.reverse()
        elif i == 'D':
            if nums:
                nums.popleft()
            else:
                print('error')
                temp = 1
                break
    if temp == 0:
        print('['+','.join(nums)+']')

두 번째 코드 - 통과, reverse하는 횟수를 최소로 하기 위해, 'R'의 갯수 세어주기

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for tc in range(T):
    p = input().rstrip()
    n = int(input())
    nums = deque(input().rstrip()[1:-1].split(','))

    if n == 0:
        nums = deque()
    check = 0
    temp = 0

    for i in p:
    	# R의 갯수 세어주기
        if i == 'R':
            check += 1
        elif i == 'D':
            if len(nums) == 0:
                print('error')
                temp = 1
                break
            else:
            	# R의 갯수가 짝수면 뒤집지 않아도 되니깐 앞에서 pop()
                if check % 2 == 0:
                    nums.popleft()
                # R의 갯수가 홀수면 뒤집어야 하니까 뒤에서 pop()
                else:
                    nums.pop()

    if temp == 0:
        if check % 2 ==0:
            print('['+','.join(nums)+']')
        else:
            nums.reverse()
            print('[' + ','.join(nums) + ']')

< Reveiw >

첫번째 코드처럼 문제에 따라 순차적으로 풀어줬었다. 골드 문제라기에 너무 쉬워서 뭐지 싶었는데 역시나 시간 초과..ㅎㅎ

(쉽지 않아..) 무튼 그래서 어떻게 시간 초과를 해결해야 하나 이리저리 만져보다가 혼자 생각했을 때, reverse 때문인지 생각을 못해서 다른 분들의 블로그를 보고 파악했다. 이 문제는 'R'의 갯수가 홀수면 reverse 함수를 실행하고, 짝수면 그대로 두어서 reverse를 한번만 해 시간을 줄이는 것이 핵심인 것 같다.

핵심을 알고 그에 따라 문제를 풀어나가니 무사히 통과!!

조금만 더 생각할걸, 괜히 골드에 쫄아서 뭔가 더 어려운 것이 있나 해서 충분히 혼자서 풀 수 있음에도 다른 분들의 코드를 참고한 것이 좀 아쉬웠다. 깊이 생각하는 버릇을 들이자!!

< 문제 출처 >

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