[백준/Python] AC

📄 문제

백준
난이도 : Gold 5
문제 제목 : AC

✏️ 풀이 1

import sys
from collections import deque

t = int(sys.stdin.readline())

for _ in range(t):
    p = sys.stdin.readline().strip()
    n = int(sys.stdin.readline())
    deq = deque(sys.stdin.readline()[1:-2].split(','))
    error_flag = False
    reverse_count = 0

    if list(deq) == [''] and 'D' in p:
        print('error')
        continue
    
    for func in p:
        if func == 'R':
            reverse_count += 1
        else:
            if deq:
                if reverse_count % 2 == 0:
                    deq.popleft()
                else:
                    deq.pop()
            else:
                error_flag = True
                break

    if error_flag:
        print('error')
    else:
        if reverse_count % 2 == 0:
            print('[' + ','.join(deq) + ']')
        else:
            deq.reverse()
            print('[' + ','.join(deq) + ']')

데크(deque)의 pop()과 popleft()를 이용하여 요소 삭제 시 시간복잡도를 최소한( $O(1)$ )으로 하였다.
그리고 R이 입력됐을 때마다 deq를 reverse() 해주면 시간복잡도가 $O(n^2)$이 되기 때문에 reverse_count 를 두어 처리하도록 하였다. (reverse() 연산은 기본적으로 시간복잡도가 $O(n)$이다.)

✏️ 풀이 2

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    p = list(map(len, input().rstrip().replace('RR', '').split('R')))
    n = int(input())
    if n == 0:
        input()
        arr = []
    else:
        arr = input().strip('[]\n').split(',')

    # 앞에서부터 제거할 요소들의 개수를 담은 리스트(p[0::2])의 요소들을 합산
    # 즉, front는 앞에서부터 제거할 요소의 개수
    front = sum(p[0::2])
    try:
        # 뒤에서부터 제거할 요소들의 개수를 담은 리스트(p[1::2])의 요소들을 합산
        # 즉, back은 뒤에서부터 제거할 요소의 개수
        back = sum(p[1::2])
    except:
        back = 0

    # 제거할 요소의 수가 n을 넘어서면
    if front + back > n:
        print('error')
        continue
    else:
        # 요소를 제거
        arr = arr[front:(n - back)]
    
    if (len(p) + 1) % 2 == 1:
        arr.reverse()
    print('[' + ','.join(arr) + ']')

다른 사람이 푼 풀이인데, R이 2번 연속 입력 시에는 두번 뒤집히니 그대로이고, R이 한 번 입력되면 좌우반전 되는 부분을 잘 이용하여 푼 풀이이다.
입력된 수행할 함수 문자열을 R을 기준으로 split()하여
나눠진 문자열의 길이, 즉 D의 개수를 요소로 한 리스트 p 를 만들었다.
그리고 이를 이용하여 홀수번째 요소는 앞에서부터 제거할 요소의 수로 보고, 짝수번째 요소는 뒤에서부터 제거할 요소의 수로 보아 과정을 진행하였다.

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '5430. AC'
GitHub - [7강] 덱/응용문제 '5430. AC'

---

처음에는 R이 나올때마다 reverse()를 적용하면서 풀었었는데, 풀면서도 시간초과가 날 것 같다는 생각이 들었다. 역시나 시간초과가 나는 것을 보고, '✏️ 풀이 1'의 방식으로 구현을 하였다.
문제 자체는 별로 어렵다고 생각하지는 않지만, 이 문제를 풀면서 입력 범위가 어느정도일 때 시간복잡도를 어떤 크기로 잡아야 하는가에 대해 생각해보게 되었다.
결론적으로, 아래와 같이 시간복잡도를 고려하여 문제를 풀어야 한다는 것을 알게 되었다.

🍏 입력 범위에 따른 적절한 시간복잡도

1. 범위가 대놓고 몇억 : 이분탐색
2. 십만~백만 : $O(N)$, $O(NlogN)$
3. 몇천 : $O(N^2)$