Baekjoon 5430.py [AC]

hohooodo·2021년 7월 22일
0

Problem Solving

목록 보기
27/32
post-thumbnail

문제가 궁금하다면?

내 풀이

import sys
from collections import deque
input = sys.stdin.readline


for _ in range(int(input())):
    func = input().rstrip()
    l = int(input())
    arr = input().rstrip()
    if l > 0:
        nums = deque(list(map(int, arr[1:-1].split(','))))
    else:
        nums = []
    leftPop = True
    result = True

    for i in func:
        if i == 'R' and leftPop:
            leftPop = False
        elif i == 'R' and not leftPop:
            leftPop = True
        elif i == 'D' and leftPop:
            if not nums:
                result = False
                break
            nums.popleft()
        elif i == 'D' and not leftPop:
            if not nums:
                result = False
                break
            nums.pop()

    if result:
        numsFinal = list(nums)
        if func.count('R') % 2 == 0:
            print('['+','.join(map(str, numsFinal))+']')
        else:
            print('['+','.join(map(str, numsFinal[::-1]))+']')
    else:
        print('error')

풀이 복기

보통의 입력과 다르게 숫자 입력이 [1,2,3] 이런식으로 들어와서 처리하는데 시간이 걸렸다.
deque(list(map(int, arr[1:-1].split(',')))) split을 사용해서 콤마를 없애고, 인덱스 슬라이싱으로 숫자만 잘랐다.

R이 리스트 뒤집기, D가 맨 앞 요소 삭제하기를 구현해야했는데. 입력 받을때마다 뒤집기, 삭제하기를 반복하면 시간초과날것같아서 R이 몇번 들어온지 True/False로 확인했다.
홀수번 뒤집었을때는 맨 뒤 요소를 삭제했고, 짝수번 뒤집었을때는 맨 앞 요소를 삭제했다. 이때문에 list가 아닌 deque를 사용해 시간을 줄이려했다.

마지막 출력할때 deque를 뒤집어서 출력해야할 경우가 있는데 이는 numsFinal[::-1]로 뒤집어줬다.

  • 리스트 요소를 거꾸로 만드는방법
    1. list[::-1]
    2. list.reverse()
    3. newList = reversed(list)

R이 몇번 입력되었는지 func.count('R')로 확인했는데, 위에 이미 선언해놓은 True/False를 확인하면 시간을 더 줄일수 있었을것같다.

  • count()의 시간복잡도는 O(n)

다른 풀이를 보며

왼쪽, 오른쪽에서 요소를 바로바로 삭제하는방법대신 개수를 세어서 한번에 계산하면 시간이 더 줄어듦

profile
글을 잘쓰는 개발자가 되고싶습니다

0개의 댓글