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

예제

조건

• 시간 제한: 1초
• 메모리 제한: 256MB

초기 코드

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):         
    command = input().rstrip()  # 명령어
    n = int(input())            # 정수의 개수
    
    if n == 0:
        nums = input().rstrip()
        print('error')
        continue
        
    nums = deque(map(int,input().lstrip('[').rstrip(']\n').split(',')))
    
    temp = True
    for c in command:
        if c == 'R':
            nums.reverse()
        elif c == 'D':
            if not nums:
                temp = False
                break
            nums.popleft()
            
    if temp:
        nums = list(nums)
        print('[',end = '')
        if nums:
            for i in range(len(nums)-1):
                print(nums[i],',', sep = '', end = '')
            print(nums[-1], end = '')
        print(']')
    else:
        print('error')

🤔 문제를 처음 보았을 때는, 간단하게 deque로 reverse와 popleft만 사용해 풀 수 있을 줄 알았다. 하지만 R이 나올 때마다 reverse를 해주는 것은 굉장히 시간을 많이 잡아먹어 결국 시간초과가 발생했다...

🔔 이 문제의 핵심은, reverse를 직접 사용하지 않고도 reverse 시키는 것이었다! 서칭을 통해 알아본 결과 아래와 같은 코드를 작성할 수 있었다.

수정 코드

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):   
     
    command = input().rstrip()  # 명령어
    n = int(input())            # 정수의 개수
    Q = deque()
    nums = input().rstrip()
    if n > 0:
        for i in nums[1:-1].split(','):
            Q.append(i)
    
    error = False
    R_cnt = 0
    
    for j in command:
        if j == 'R': 
            R_cnt += 1
        elif j == 'D' and len(Q) == 0:  # 에러가 나오는 경우
            error = True
            break
        else:
            if R_cnt % 2 == 0: # 정방향일 경우
                Q.popleft() 
            else:              # 역방향일 경우
                Q.pop()
                
    if R_cnt % 2 == 1: 
        Q.reverse()
    
    if error:
        print('error')
    else:
        print('[' + ','.join(list(Q)) + ']')
          
    

1. 입력

• 입력받은 정수들의 양 끝 대괄호들을 제거하고, deque에 넣어준다.

2. 명령어 해석

• 'R'이 나오면, R_cnt를 1 더해준다.

• 'D'가 나왔는데 Q가 빈 경우, error를 출력해준다.

• 'D'가 나온 경우, 현재 R_cnt가 홀수라면 (= 뒤집힌 경우) 마지막 원소를 제거하고, 짝수라면 (= 원래의 방향) 첫 번째 원소를 제거한다.

• 이는 'RR'과 같이 'R'이 짝수로 연속으로 나오는 경우에는, 배열이 기존과 동일함을 이용하는 것이다.

• 최종적인 R_cnt의 상태가 홀수라면, 실제로 reverse를 진행해준다.

3. 출력

• 출력 형식을 맞춰주기 위해, join을 사용하여 출력해준다.

느낀 점 & 배운 점

1. 역시 레벨이 높아질수록 간단한 메소드로 풀 수 있는 문제는 줄어드는 것 같다. 메소드를 사용하지 않고도 사용한 것처럼 구현하는 능력이 필요한 것 같다.

2. reverse를 실제로 사용하지 않고도 풀어내는 과정이 인상적이었던 문제였다!