(Python) 백준 5430

백준 5430

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	102808	22785	16071	19.833%

문제

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

---

답안

import sys

def get_input() -> (str, list[int]):
    operations = sys.stdin.readline().rstrip()
    _ = sys.stdin.readline()
    line = sys.stdin.readline().strip('[]\n').split(',')
    if line[0] == '':
        line = []
    arr = list(map(int, line))
    return operations, arr

def solve(operations: str, arr: list[int]) -> None:
    start = 0
    end = len(arr)
    is_reversed = False
    for op in operations:
        if op == 'R':
            is_reversed = not is_reversed
        else:
            if is_reversed:
                end -= 1
            else:
                start += 1
    if start > end:
        print('error')
        return
    arr = list(map(str, arr[start:end]))
    if is_reversed:
        print('['+','.join(reversed(arr))+']')
    else:
        print('['+','.join(arr)+']')

if __name__ == '__main__':
    num_testcase = int(sys.stdin.readline())
    for _ in range(num_testcase):
        operations, arr = get_input()
        solve(operations, arr)

풀이

단순 구현하니 문제가 풀렸다.

문제 조건에서 p의 길이의 합과 n의 합이 70만을 넘지 않는다고 했으니, O(n)의 시간복잡도로 문제를 풀면 되겠다는 생각이 들었고,

R 연산이 입력되었을 때 실제로 숫자 배열을 뒤집는 것이 아니라 start와 end라는 두 정수를 이용해 출력할 범위를 나타내면 되겠다는 생각을 했다.

def get_input() -> (str, list[int]):
    operations = sys.stdin.readline().rstrip()
    _ = sys.stdin.readline()
    line = sys.stdin.readline().strip('[]\n').split(',')
    if line[0] == '':
        line = []
    arr = list(map(int, line))
    return operations, arr

입력을 받는 함수이다. 만약 빈 숫자 배열이 입력으로 주어지면, line이 ['']이 되게 되므로, 이 상태에서 map(int, line)을 실행하면 int 함수에 빈 문자열을 넣어주게 되므로(int(’’)) 에러가 발생한다.

따라서 line이 ['']이면 line을 아예 비워주었다.

def solve(operations: str, arr: list[int]) -> None:
    start = 0
    end = len(arr)
    is_reversed = False
    for op in operations:
        if op == 'R':
            is_reversed = not is_reversed
        else:
            if is_reversed:
                end -= 1
            else:
                start += 1

start와 end는 각각 결과로 출력할 숫자 부분배열의 처음과 끝을 나타내는 정수이다.

is_reversed는 배열이 현재 뒤집혀져 있는지 아닌지를 검사하고, 만약 뒤집혀져 있는 상태에서는 end를 1 감소시키고, 그대로인 상태에서는 start를 1 증가시킴으로써, 출력될 숫자 부분배열에서 끝/처음 부분을 제외시킨다.

    if start > end:
        print('error')
        return
    arr = list(map(str, arr[start:end]))
    if is_reversed:
        print('['+','.join(reversed(arr))+']')
    else:
        print('['+','.join(arr)+']')

만약 start가 end보다 큰 값을 가지게 된다면, 이것은 배열의 크기보다 더 많은 수의 D 연산을 수행했음을 알려준다.

출력할 숫자 부분배열의 범위는 start부터 end-1까지의 값이므로, start가 end와 같은 값을 가지게 된다면, 출력할 숫자 부분배열이 빈 배열임을 나타낸다.

경계값에 주의하여, 만약 배열이 뒤집혀진 상태라면 (R 연산이 홀수 번 수행되었다면) 배열을 뒤집어 출력한다.

if __name__ == '__main__':
    num_testcase = int(sys.stdin.readline())
    for _ in range(num_testcase):
        operations, arr = get_input()
        solve(operations, arr)

이 모든 과정을 각각의 테스트케이스에 대해 수행하면 정답으로 인정된다.