5430번 - AC

💡 함부로 파이썬 메소드를 사용하지 말고, 시간복잡도 측면에서 더 나은 코드가 있는지 확인해보자!!

<시간 초과 코드>

import sys
from collections import deque

input = sys.stdin.readline

T  = int(input())

for _ in range(T):
    
    func = deque(input().rstrip())
    num = int(input())
    element = input().rstrip()
    
    dq = deque(element[i] for i in range(1,(num*2+1),2))
    flag = 0

    while func:
        
        if func.popleft() == 'R':
            dq.reverse()
        else:
            if dq:
                dq.popleft()
            else:
                flag = 1
                break

    if flag != 1:            
        print(list(map(int,dq)))
    else:
        print("error")

• 이 문제는 문제를 풀이하는 것보다, 시간 복잡도 측면에서의 구현과 입출력의 반례를 찾아서 해결하는 것이 가장 핵심이 였던거 같다.
• 비교적 쉽게 첫번째 코드가 도출되었지만..ㅎ 역시나 시간초과가 발생하였다.
• 따라서 원인을 분석해본 결과 R이 들어올 때마다, reverse()를 사용하여 역전시키는 코드가 시간복잡도 적인 측면에서 시간초과를 일으킨 것 같았다.

< 런타입 에러 코드 >

import sys
from collections import deque

input = sys.stdin.readline

T  = int(input())

for _ in range(T):
    
    func = deque(input().rstrip())
    num = int(input())
    element = input().rstrip()
    
    dq = deque(int(element[i]) for i in range(1,(num*2+1),2))
    
    flag = 0
    # reverse 여부로, 뒤집히면 flag가 바뀐다 ( 정상: 1, 반대: -1 )
    rflag = 1

    while func:
        
        if func[0] == 'R':
            rflag *= -1
        elif func[0] == 'D' and rflag == 1:
            if dq:
                dq.popleft()
            else:
                flag = 1
        elif func[0] == 'D' and rflag == -1:
            if dq: 
                dq.pop()
            else:
                flag = 1 
        
        func.popleft()
    
    if flag != 1 and rflag == 1:
        print(list(dq))
    elif flag != 1 and rflag == -1:
        print(list(reversed(dq)))
    else:
        print("error") 

• 이 코드는 시간 복잡도 측면에서 해결하기 위해서, reverse()를 매번쓰지말고, "R"이 등장할 때마다 rflag를 바꿔가면서 현재 넣어야할 방향이 정방향인지, 반대방향인지를 파악하여 데이터를 넣어줬다. (이럴때, deque가 사용되구나.. 하고 생각했다)
• 하지만 시간초과의 문제는 해결되었지만, 처음 dq를 저장하는 부분과 출력부분에서 계속 문제가 발생하였는지 런타임 에러가 발생하였다.
• 문제점을 계속 분석해본 결과 문제점은 2가지 였다.
  => 1. num = 0 일 경우 []가 들어가는데 위와 같이 dq로 선언하면, ]만 들어가는 문제
  => 2. deque나 list는 출력 자체가 [1, 2, 3, 4] 이런식으로 ,다음에 띄어쓰기가 들어가는데 출력해야하는 것은 띄어쓰기가 없는 [1,2,3,4]였다.

<정답 코드>

import sys
from collections import deque

input = sys.stdin.readline

T  = int(input())

for _ in range(T):
    
    func = deque(input().rstrip())
    num = int(input())
    # num에 0이오면 무시할 수 있도록 설정
    dq = deque(map(int,input()[1:-2].split(','))) if num > 0 else deque(input()[1:-2])
    
    flag = 0
    # reverse 여부로, 뒤집히면 flag가 바뀐다 ( 정상: 1, 반대: -1 )
    rflag = 1

    while func:
        
        if func[0] == 'R':
            if dq:
                rflag *= -1
        elif func[0] == 'D' and rflag == 1:
            if dq:
                dq.popleft()
            else:
                flag = 1
                break
        elif func[0] == 'D' and rflag == -1:
            if dq: 
                dq.pop()
            else:
                flag = 1
                break
        
        func.popleft()
    
    if flag != 1 and rflag == 1:
        print("[",end='')
        for i in range(len(dq)):
            print(dq[i], end=',' if i != len(dq) - 1 else '')
        print("]")
    elif flag != 1 and rflag == -1:
        print("[",end='')
        for i in range(len(dq)-1,-1,-1):
            print(dq[i], end=',' if i != 0 else '')
        print("]")
    else:
        print("error")

• 결론적으로는, 우선적으로 입력받은 요소들을 바로 deque로 넣어주면서 조건을 걸어 num=0인 즉, []가 들어오는 경우를 다르게 처리하여 주었다.
• 또한 출력부분에서도 reverse()를 쓰고 나서 순회를 돌면서 처리하면 결국 2n이 들기 때문에 역으로 돌려주는 방식을 사용하여 거꾸러 출력해주었디.
• 마지막으로 출력은 [1,2,3,4]와 같은 방식으로 출력될 수 있도록 수정해주었다.

💡 코테스터디에서 나온 기발한 풀이법

• 혜진님 : join을 사용하여 출력 시간을 많이 줄이셨다.
  => print('[' + ','.join(q) +']')

• 서현님: pop()과 popleft()를 사용하지 않고, index로만 진행하였다.

 for _ in range(T):
    P = s.readline().rstrip()
    N = int(s.readline())
    
    try:
        A = list(map(int, s.readline().rstrip()[1:-1].split(',')))
    except:
        A = []
    cnt_d = P.count("D")
    if cnt_d > N:
        print('error')
        continue
    else:
        ind_front = 0
        ind_back = N-1
        rev = 1
        for p in P:
            if p == 'R':
                tmp = ind_front
                ind_front = ind_back
                ind_back = tmp
                rev *= -1
            else:
                ind_front += rev
        res = [A[ind] for ind in range(ind_front, ind_back+rev,rev)]
        print(f"[{",".join(map(str, res))}]")

=> pop()을 직접적으로 이용하지 않고, pop되는 index만 범주에서 제거하면서 출력 범주를 줄이는 방식을 사용하셨다.