[solved.ac 골드5] 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를 출력한다.

예제

 

---

나의 풀이

이 문제의 가장 쉽게 생각할 수 있는 풀이는 정말로 R이 들어오면 배열을 뒤집고, D가 들어오면 맨 앞의 요소를 제거하는 것이다.

파이썬의 리스트의 경우 배열을 뒤집은 것은 O(n)만큼, 맨 앞의 요소를 제거하는 것 역시 O(n) 만큼의 시간 복잡도가 소요된다.

이 문제의 입력 조건을 보면

• T(테스트 케이스): 최대 100
• p(수행할 함수): 최대 100,000
• n(배열에 들어있는 수의 개수): 최대 100,000
• p 길이의 합, n 길이의 합: 최대 70만 이다.

즉, 최악의 상황에 T * n 길이 합 * p 길이 합 = 100 * 70만 * 70만 = 49,000,000,000,000 (49조) 이다.

1초에 1억번의 연산을 한다고 했을 때 49만초 = 56712일과 23시간6분40초 = 대략 156년이 소요된다.

이번 생은 글렀다

 

암튼 이 문제는 새로운 풀이법을 생각해야 한다.

우선 D가 들어와서 맨 앞의 요소를 제거하는 것은 Queue 자료구조를 사용하면 된다. (파이썬에서는 Deque)

Queue에서 맨 앞 요소를 제거하는 시간 복잡도는 O(1) 이기 때문에 최대 70만배는 빨라질 것이다.

여전히 시간 초과가 발생할 것이다. 리스트를 뒤집는 작업을 O(n)이 아닌 훨씬 빠른 속도가 필요하다.

 

나는 이를 투 포인터를 사용해 풀이했다.

리스트를 뒤집는 것은 사실 뒤집었을 때 뒤에서부터 앞으로 읽으면 그만이다. 그것도 매번 읽는 것이 아니라 최종적으로 정방향인지 역방향인지만 알면 마지막에 그렇게 읽으면 된다.

대신 역방향일 때 D가 들어오면 맨 앞이 아닌 맨 뒤의 요소를 제거해야한다. (그래야 뒤집었을 때 맨 앞이 제거되는 것이므로)

물론 투포인터이기 때문에 직접 리스트에서 빼내는 것이 아니라 그냥 인덱스만 하나 이동시켜주면 그만이다.

for _ in range(int(input())):
    cmd = input()
    n = int(input())
    d = 1  # default: 1, reversed: -1
    start, end = 0, n - 1
    suspend = False
    arr = list(input()[1:-1].split(','))

    for c in cmd:
        if c == 'R':
            d *= -1
        elif c == 'D':
            if start > end:
                print('error')
                suspend = True
                break
            elif d == 1:
                start += 1
            elif d == -1:
                end -= 1

    if not suspend:
        arr = arr[start:end + 1][::d]
        print(f"[{','.join(arr)}]")

 

 

만약 start가 end보다 커지면 리스트가 비어있다는 뜻이다. 이때 'error'를 출력하고 suspend에 True를 저장하여 추후에 사용한다.

suspend 값이 False일 때만 리스트를 출력하면 되는데 이 때 start와 end로 적절히 슬라이싱 하고, d로 출력 step을 조절할 수 있다.

d가 1이면 정방향이고, -1이면 역방향으로 출력된다. (이는 시간 복잡도가 O(1)이다)

최종적으로 arr를 ','로 묶어서 형식에 맞게 출력해주면 된다.

 

채점 결과