[백준] 5430번 AC - (Python)

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

5430번: AC

입출력 인덱싱과 R처리만 구현하면 크게 어렵지 않았던 문제. 남들은 시간초과가 발생했다고 했는데, 오히려 틀렸습니다.. 이후 정답.. 생각보다 문제에 잘 접근했었던 것 같습니다. 

시간초과를 해결하는 중요 포인트가 R에서 reverse를 최종적으로 1번만 처리하는 것입니다. 이에 대해서는 아래에서 설명하겠습니다.

※ 고려사항

1. 입력 인덱싱

2. 함수 처리

3. 출력 처리

 

---

1. 입력 인덱싱

생각보다 이 곳에서 시간을 많이 소비했습니다. split과 strip메소드를 적절하게 활용했어야 했는데, 같이 구현하는 생각을 못했습니다. 처음 생각한 방식은 strip으로 모든 요소를 인덱싱 후, [ ] 를 없애기 위해 젤 앞과 맨 뒤 요소만 삭제했습니다. 그러나 42와 같은 십의자리 이상의 숫자도 분해하는 문제가 발생했습니다. 따라서 구간을 나눈 정한 곳에서 인덱싱을 해야합니다.

코드는 다음과 같습니다.

    # 함수 list
    f = list(map(str, input().strip()))

    # 배열 크기
    num = int(input())
    
    # 덱에 배열 삽입
    queue = deque(input().rstrip()[1:-1].split(","))

단, 여기서 중요한 점은 마지막 예시와 같이 [ ] 빈 배열이 들어왔을 경우, deque는 [" "]이 저장되어 아무것도 없지만 빈 상태가 아니게 됩니다. 따라서 배열의 크기가 0인 경우, 빈 덱을 새로 생성해줘야 합니다.

    # 배열크기가 0이면 빈 덱 생성
    if num == 0:
        queue = deque()

 

2. 함수 처리

이 문제의 핵심 요소입니다. 함수처리는 R과 D가 있습니다. R은 해당 요소를 뒤집어야 하고, D는 젤 앞 요소를 삭제합니다.

그렇기 때문에 양방향 삭제가 가능한 Deque 자료구조를 사용해야 합니다. 여기서 중요한 점은 R을 할 때마다 reverse 메소드를 구현하게 되면, 시간초과가 발생합니다. 따라서 이를 판별해 줄 요소가 필요합니다.

저는 flag를 통해 기본값을 False로 두고, R이 있을 때마다, flag를 T, F로 계속 변환해 주었습니다. 최종 출력 시에도, 이를 반영하여 flag가 True이면 reverse를 한 후, 출력을 하게 합니다. 코드는 다음과 같습니다.

    # reverse check
    flag = False

    # 함수 list
    f = list(map(str, input().strip()))

    # 배열 크기
    num = int(input())
    
    # 덱에 배열 삽입
    queue = deque(input().rstrip()[1:-1].split(","))

    # 배열크기가 0이면 빈 덱 생성
    if num == 0:
        queue = deque()

    for j in f:
        # R일때, flag 변경
        if j == 'R':
            if flag == True:
                flag = False
            else:
                flag = True

        # 삭제
        elif j == 'D':
            # 빈 배열 아닐때, flag유무로 삭제
            if len(queue) != 0:
                if flag == True:
                    queue.pop()
                elif flag == False:
                    queue.popleft()

            # 비었다면 error
            else:
                print('error')
                break

 

3. 출력 처리

앞서 언급드린 거와 같이, flag를 통해 반별한 후, True값이면 reverse를 시켜 출력합니다. 다음과 같습니다.

    else:
        if flag == False:
            print("[" + ",".join(queue) + "]")
        else:
            queue.reverse()
            print("[" + ",".join(queue) + "]")

---

전체코드

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    
    # reverse check
    flag = False

    # 함수 list
    f = list(map(str, input().strip()))

    # 배열 크기
    num = int(input())
    
    # 덱에 배열 삽입
    queue = deque(input().rstrip()[1:-1].split(","))

    # 배열크기가 0이면 빈 덱 생성
    if num == 0:
        queue = deque()

    for j in f:
        # R일때, flag 변경
        if j == 'R':
            if flag == True:
                flag = False
            else:
                flag = True

        # 삭제
        elif j == 'D':
            # 빈 배열 아닐때, flag유무로 삭제
            if len(queue) != 0:
                if flag == True:
                    queue.pop()
                elif flag == False:
                    queue.popleft()

            # 비었다면 error
            else:
                print('error')
                break
                
    else:
        if flag == False:
            print("[" + ",".join(queue) + "]")
        else:
            queue.reverse()
            print("[" + ",".join(queue) + "]")

---

생각보다 입력에서 시간을 많이 사용했습니다. 자료구조, 그래프 등 알고리즘 구현에만 신경 쓰다 보니 기본적인 요소를 처리하는 부분을 많이 간과한 듯합니다. 그래서 기본의 중요성을 일깨워주었던 좋은 문제였던 것 같습니다.

설명의 오류나, 궁금하신 점은 언제든 피드백해주시면 감사하겠습니다 ^~^