백준 온라인 저널, 구현, 자료구조, 파싱, 문자열, 덱/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

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력 1

[2,1]
error
[1,2,3,5,8]
error

 

 

접근 방법

1. start와 end, step을 각각 0, n, 1로, 배열을 뒤집었는 지에 대한 정보를 나타내는 r, s를 각각 False와 True로 저장한다.

2. 수행해야할 함수 p를 순서대로 꺼냈을 때 R이나오면 D가 나올 때까지 값을 더해준다.(최적화를 위해)

3. D가 나왔을 때 연속적으로 R이 몇번 나왔는 지 센 뒤, R이 홀수번 등장할 경우 r, s의 값을 각각 바꿔준다.

4. r이 True일 경우(s는 False) end를 하나씩 빼준다.

5. r이 False일 경우(s는 True) start를 하나씩 더해준다.

6. 모든 함수가 다 출력되는 경우에는 현재 배열을 출력한다. 이때 r이 True면 배열을 거꾸로 출력해야하기 때문에 step = -1로 바꿔주고 현재 배열에서 'start'인덱스부터 'end'인덱스까지 배열의 순서에 맞게 출력한다.

7. 각 테스트 케이스마다 1번부터 6번까지 실행해준다.

 

 

코드

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    error = False
    func = sys.stdin.readline()
    n = int(sys.stdin.readline())
    string = sys.stdin.readline()
    if n >= 1:
        array = list(map(int, string[1:-2].split(',')))
    else:
        array = []

    count_r = 0
    start, end, step = 0, n, 1
    r, s = False, True
    for order in func:
        if order == 'R':
            count_r += 1

        elif order == 'D':
            if count_r % 2 == 1:
                r, s = s, r
                count_r = 0

            if start==end:
                print('error')
                error = True
                break
            else:
                if s:
                    start += 1
                else:
                    end -= 1

    if count_r % 2 == 1:
        r, s = s, r  
                    
    if not error:
        if r:
            step = -1
        result = array[start:end][::step]
        print(''.join(str(result).split(' ')))

 

- 해당 문제는 R이 나왔다고 해서 배열을 계속해서 뒤집는다면 시간 초과로 해결할 수 없는 문제이다. 함수는 총 100,000번까지 나올 수 있기에 R이 100,000번 나온다고 가정하면 배열을 100,000번 뒤집어야하기 때문에 시간복잡도에서 문제가 발생한다.

1. 뒤집는 경우가 연속적으로 주어질 경우엔 이를 다 더하고 홀수번만큼의 뒤집는 함수가 주어지면 이를 뒤집는 것을 생각해볼 수 있다.

2. 뒤집는 경우마다 r과 s를 바꿔가며 시작 인덱스와 끝 인덱스를 조정하는 방법도 생각해볼 수 있다.

 

- 위와 같이 생각하고 문제 제출을 했는데 계속 틀렸다. 게시판에 있는 모든 반례를 다 넣어도 정답이 나오고, 다시 생각해봐도 맞는 것같은데 자꾸 틀리게 나와서 꽤나 고전이었다. 

- 나중에 설마해서 확인해보니 출력 조건이 틀렸었다.

- 배열을 그대로 출력할 경우 배열의 원소 간에 공백이 있어서 출력 조건에 부합하지 않았다.

출력 조건 : [1,2,3,4]

실제 출력 : [1, 2, 3, 4]

- 오늘도 문제를 상세히 읽어봐야겠다는 교훈을 배웠다.