[백준] 5430 - AC (Python)

문제 링크

알고리즘

• 구현
• 자료 구조
• 문자열
• 파싱
• 덱

tip

• 리스트의 양쪽 모두에서 삭제가 쉬운 deque 자료구조를 활용한다.
• 시간이 오래걸리는 reverse() 연산을 최소화한다.

구현할 것들

1. 입력받은 [1,2,3,4] 형태의 문자열을 deque로 변환
2. 입력받은 R,D 함수를 for문으로 처리
3. 최종적으로 남은 deque를 [1,2,3,5,8] 형태로 출력

풀이

from collections import deque
from sys import stdin


input = stdin.readline
T = int(input())

for _ in range(T):
    functions = input().rstrip() # 'RDDRR'
    
    # 연속으로 두번 나오는 'R'을 없애준다
    functions = functions.replace("RR", "") 
    
    cnt = int(input())
    lst = input().rstrip() # '[1,2,3,4]'
    
    if len(lst) == 2:  # 빈 리스트가 들어오면 바로 처리한다
        if "D" in functions:
            print("error")
        else:
            print([])
        continue
    
    # '[1,2,3,4]' 형태의 문자열을 조작해서 deque에 넣는다
    lst = map(int, lst[1:-1].split(","))
    deq = deque(lst)

입력을 받는 코드이다. functions 변수에 'RDDRR' 형태의 문자열을 받는다. 연속으로 나오는 'R' 은 의미가 없기 때문에 replace() 함수로 없애준다.

이제 '[1,2,3,4]' 형태의 문자열을 lst 변수에 담고 조작을 거쳐 deque로 변환한다.
만약 빈 리스트가 입력으로 들어오면 명령어에 'D'가 있는지만 확인해서 바로 처리한다.

	reversing = False # False면 왼쪽에서 삭제하고 True면 오른쪽에서 삭제한다.
    
    for f in functions:
        if f == "R": # 실제로 리스트를 뒤집지 않는다.
            reversing = not reversing
        else:
            if len(deq) == 0:
                print("error")
                # for else: break 문에 걸리면 else 문으로 넘어가지 않는다
                break 

            if reversing:
                deq.pop()
            else:
                deq.popleft()
    else:
        if reversing: # 만약 마지막에 'R'이 하나 남았다면 deque를 뒤집는다.
            deq.reverse()
        print_deque(deq) # deque를 출력해서 마무리

이제 함수를 처리한다. 'R' 함수에서 실제로 리스트를 뒤집지 않는다. 대신 reversing 변수의 값을 스위치하면서 왼쪽에서 값을 뺄 것인지 오른쪽에서 뺄 것인지를 결정한다.

그리고 리스트의 길이가 0일 때 'D' 함수가 들어오면 error를 출력하고 break 문을 통해 빠져나온다.

for 문이 끝나면 리스트를 한번 뒤집어야 하는지 확인하고 print_deque() 함수를 호출한다. 하지만 아까 break 문으로 빠져나와서도 출력하는 코드가 실행되면 안되기 때문에 for else 문으로 처리한다. (for 문에서 break 문으로 빠져나오면 else 문으로 넘어가지 않는다.)

def print_deque(deq):
    if len(deq) == 0:
        print([])
    else:
        res = "["
        for i in range(len(deq) - 1):
            res += f"{deq[i]},"
        res += f"{deq[-1]}]"
        print(res)

마지막으로 deque를 출력하는 함수이다.
단순히 리스트로 변환해서 출력하면 [1, 2, 3, 5, 8] 형태로 출력되는데 이는 빈칸 때문에 오답처리된다. 따라서 [1,2,3,5,8] 의 형태로 출력하는 함수를 따로 만들어준다.

전체 코드

from sys import stdin
from collections import deque

input = stdin.readline


def print_deque(deq):
    if len(deq) == 0:
        print([])
    else:
        res = "["
        for i in range(len(deq) - 1):
            res += f"{deq[i]},"
        res += f"{deq[-1]}]"
        print(res)


T = int(input())

for _ in range(T):
    functions = input().rstrip()
    functions = functions.replace("RR", "") 
    cnt = int(input())
    lst = input().rstrip()
    
    if len(lst) == 2:  # []
        if "D" in functions:
            print("error")
        else:
            print([])
        continue
        
    lst = map(int, lst[1:-1].split(","))
    deq = deque(lst)


    reversing = False
    
    for f in functions:
        if f == "R":
            reversing = not reversing
        else:
            if len(deq) == 0:
                print("error")
                break
            if reversing:
                deq.pop()
            else:
                deq.popleft()
    else:
        if reversing:
            deq.reverse()
        print_deque(deq)