[백준] AC (5430번) - Python

✅문제 - AC(5430번)

---

 

✅아이디어

---

🔵문제 조건

시간제한이 1초 이므로 연산을 2000만 번 안에 끝내야 한다. (Python 은 1초에 2000만 번의 연산을 한다고 가정하자)
이때 함수의 최대 길이가 100,000이므로 시간 복잡도가 O(N^2)을 넘으면 시간 초과에 걸리게 된다.

🔵실패 했던 아이디어

실제로 R인 경우에는 reverse를 D인 경우에는 pop을 실행했다.
이때 함수의 길이만큼 for문을 돌려야 하고 그 안에서 if 문을 돌려야 하므로 시간 복잡도가 O(N^2)이 된다.

정말 처참한 결과다

🔵성공한 아이디어

실제로 pop 이나 reverse를 진행하지 않는 방법을 생각했다.
1. 함수에서 RR이 나오면 순서가 바뀌지 않으므로 입력받은 함수에서 replace("RR","")을 통해 모든 RR을 지워 준 후에 .split("R")을 해준다.
2. 이를 통해 얻은 list는 정방향 pop과 역방향 pop의 list가 된다.
3. 이를 실제로 진행하는 것이 아니라 len method를 통해 pop 하는 횟수만 계산한다.
이 때 front는 정방향 pop의 개수 back은 역방향 pop의 개수이고 end는 back을 고려한 끝나는 idx를 계산한 것이다.
4. 출력해야하는 함수가 reverse 인지 아닌지 알기 위해 len(함수) - front - back % 2를 해준다.
R이 짝수개면 정방향 홀수개면 역방향이다.
5. 출력은 앞서 구한 front부터 end를 출력한 후 역방향인 경우에는 reverse를 아닌 경우에는 그대로 출력한다.

✅코드

---

import sys
from collections import deque

input = sys.stdin.readline

n = int(input().rstrip())
is_reverse = False

for _ in range(n):
    command = input().rstrip()
    length = int(input().rstrip())
    num_list = list((input().rstrip()[1:-1]+",").split(","))
    num_list.pop()

    front = 0
    back = 0
    command_list = command.replace("RR","").split("R")
    for i in command_list[0::2]:
        front += len(i)
    for i in command_list[1::2]:
        back += len(i)
    end = length-back

    if front + back > length:
        print("error")
    else:
        if (len(command) - front - back) % 2 == 0 :
            is_reverse = False
        else:
            is_reverse = True

        if is_reverse:
            print(f'[{",".join(reversed(num_list[front:end]))}]')
        else:
            print(f'[{",".join(num_list[front:end])}]')