백준 5430번: AC (Python)

 

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

5430번: AC

---

Level: Gold V

Solved By: String (split)

 

1. 문자열 split

 

입력이 까다로운 문제입니다. 파이썬에서는 이러한 문자열에 대해 핸들링을 할 수 있는 split()라는 함수가 있으며, delimiter를 ', '로 할당하여 분리를 해준 뒤에 맨 앞 원소와 맨 마지막 원소에 담겨있는 '[', ']'를 없애줍니다.

 

2. 모든 reverse를 처리하면 시간 초과다.

 

제가 알기로는 reverse 함수는 O(N)으로 알고 있습니다. 만약 n의 길이가 100,000으로 잡히고, p의 최대치인 100,000번을 모두 reverse 해야 한다면, 여러 테스트 케이스를 한 번에 처리해야 하는 문제로 시간 초과가 날 것입니다.

 

이 문제에 대한 해결 방법으로는 reverse를 하지 않았을 때, 몇 개의 원소를 삭제하는지, reverse를 했을 때 몇 개의 원소를 삭제하는지 모두 기억하여 두었다가 마지막에 이를 적용해 주면 됩니다.

 

그리고, 예외 상황으로 Delete 명령이 배열의 원소 길이보다 크다면 'error'라고 알려주어야 하고, Reverse가 몇 번 호출되었는지에 따른 마지막에 reverse가 되어있어야 하는지 아닌지를 따져주어야 합니다.

import sys

T = int(input())

def getCommand(command):
    ret = []
    for i in range(0, len(command)):
        if command[i] == "R":
            ret.append(0) # 0 - reverse
        elif command[i] == "D":
            ret.append(1) # 1 - delete
    return ret
    
def getNum(li_str):
    if len(li_str) <= 2: # base-case, []
        return []
    
    li_str = li_str.split(",")
    # 첫 원소 '[' 제거
    li_str[0] = li_str[0][1:]
    # 마지막 원소 ']' 제거
    li_str[len(li_str)-1] = li_str[len(li_str)-1][:-1]
    
    ret = []
    for v in li_str:
        ret.append(int(v))
    return ret
    

final_res = []

for t in range(0, T):
    command = input()
    n = int(input())
    li_str = input()
    
    command_li = getCommand(command)
    num_li = getNum(li_str)
    
    r_cnt = 0
    d_l_cnt = 0
    d_r_cnt = 0
    flag = True # if True -> left, if False -> right
    for rd in command_li:
        if rd == 0:
            flag = True if flag == False else False
            r_cnt += 1
        elif rd == 1:
            if flag == True:
                d_l_cnt += 1
            else:
                d_r_cnt += 1
    
    # print(num_li)
    if (d_l_cnt + d_r_cnt) > n:
        final_res.append("error")
    else:
        # 앞에 자르기
        num_li = num_li[d_l_cnt:]
        # 뒤에 자르기
        num_li = num_li[:len(num_li)-d_r_cnt]
        if r_cnt % 2 == 1:
            num_li.reverse()
        final_res.append(num_li)

# print(len(final_res))
for q in final_res:
    if q == "error":
        print(q)
    else:
        print('[',sep='',end='')
        for i in range(0, len(q)):
            print(q[i], sep='', end='')
            if i == len(q) - 1:
                continue
            print(',', sep='', end='')
        print(']',)