[Python] 백준 5430 AC_문자열과 deque

https://www.acmicpc.net/problem/5430

5430번: AC

 

문제 풀기

1. t, p , n 그리고 배열 형태인 정수들을 입력 받는다.
2. 입력받은 정수는 [1, 2, 3, 4] 👉 이런식으로 문자열 형태 이기 때문에 문자열 슬라이싱을 사용해 앞 뒤 대괄호 [] 를 제거한다.
   nums = sys.stdin.readline().rstrip()[1:-1]
3. 쉼표(,) 로 파싱한 뒤 리스트로 만들어 덱을 생성한다.
   nums = deque(nums.split(','))
   👉 이때 입력받은 문자열이 '[]' 처럼 빈 배열이면 파싱할 내용이 없기 때문에 길이 체크를 통해 빈 덱을 생성해줘야한다.
4. 반복문으로 입력받은 p에 저장된 함수에 접근하여 R 또는 D연산을 수행한다.
   - R을 만나면 정수 배열을 reverse 해야한다. 👉 이 방법은 시간을 많이 소요한다.
   원래는 D 일 때 앞의 데이터를 삭제하지만 reverse인 상태에서는 뒤에서 데이터를 삭제하도록 했다. reverse 여부를 기억하기 위한 변수 r_flag를 운영했다.
   - deque에 데이터가 없는 경우 D를 하려고 하면 'error'를 출력한다.
5. 출력할 때도 배열의 형태로 출력해야하기 때문에 join함수로 배열의 요소들을 하나의 문자열로 만든뒤, 앞 뒤에 대괄호[]를 붙여 출력한다.

 

시도 1 - 실패

import sys
from collections import deque
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    p = sys.stdin.readline().rstrip()
    n = int(sys.stdin.readline().rstrip())
    nums = sys.stdin.readline().rstrip()[1:-1]
    if len(nums) > 0:
        nums = deque(nums.split(','))
    else:
        nums = deque()
    
    for func in p:
        if func == 'R':
            nums.reverse()
        elif func == 'D':
            if len(nums) > 0:
                nums.popleft()
            else:
                nums = ['error']
                break
            
    result = ','.join(nums)

    if result == 'error':
        print(result)
    else:
        print(f'[{result}]')

맨 처음엔 R을 만날 때마다 list의 reverse() 함수를 호출했는데, 시간초과가 났다.
list 의 reverse()  함수는 모든 원소의 위치를 역순으로 바꾸기때문에 O(n)의 복잡도를 가진다.

👉 n은 최대 100,000개, p의 길이도 최대 100,000까지 될 수도 있다.
최악의 경우 100,000개의 숫자를 담고있는 배열을 100,000 번 'R'을 (reverse) 수행해야한다.
100,000번(p)의 루프를 돌면서 n개를 뒤집어버리는 O(n)의 복잡도가 곱해지는 거니까 100,000 * 100,000 = 1,000,000,000 -> 10억번의 연산을 해야하니 시간 초과 오류가 날 수 밖에

 

 

시도 2

import sys
from collections import deque
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    p = sys.stdin.readline().rstrip()
    n = int(sys.stdin.readline().rstrip())
    nums = sys.stdin.readline().rstrip()[1:-1]
    if len(nums) > 0:
        nums = deque(nums.split(','))
    else:
        nums = deque()
    r_flag = False
    for func in p:
        if func == 'R':
            r_flag = not r_flag
        elif func == 'D':
            if len(nums) > 0:
                if r_flag:
                    nums.pop()
                else:
                    nums.popleft()
            else:
                nums = ['error']
                break
    if r_flag:
        nums.reverse()

    result = ','.join(nums)

    if result == 'error':
        print(result)
    else:
        print(f'[{result}]')

r_flag를 운영해서 R을 만날 때 True/False로 전환시켜, 'D' 명령을 받았을 때 r_flag가 True면 리스트의 뒤에서부터 삭제하는 pop(), False면 리스트의 앞에서 삭제하는 popleft()를 호출했다.
함수를 모두 수행하고 난 뒤에도 여전히 r_flag가 True면 reverse한 뒤 출력했다.

🥳 성공!

 

최종소스_개선

error를 출력하는 부분이 if 문 depth가 깊어져서 맘에 안들었다.
개선하기 위해 고민해보니 맨 처음에 리스트 nums의 길이보다 'D'의 개수가 많으면 error를 출력하면 될 것 같아 또 수정했다.

import sys
from collections import deque
t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    p = sys.stdin.readline().rstrip()
    n = int(sys.stdin.readline().rstrip())
    nums = sys.stdin.readline().rstrip()[1:-1]
    if len(nums) > 0:
        nums = deque(nums.split(','))
    else:
        nums = deque()

    if p.count('D') > len(nums):
        print("error")
        continue

    r_flag = False
    for func in p:
        if func == 'R':
            r_flag = not r_flag
        elif func == 'D':
            if r_flag:
                nums.pop()
            else:
                nums.popleft()
    if r_flag:
        nums.reverse()

    result = ','.join(nums)
    print(f'[{result}]')

👍 보다 보기 좋아졌다.

 

 

우당탕탕 성공완