[Baekjoon] 5403번 : AC (Python, 문자열)

[Baekjoon] 5403번 : AC (Python, 문자열)

 

목차

 

 

 

 

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

5430번: AC

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 -  코드 길이 539B

 

import sys
input = sys.stdin.readline

for i in range(int(input())):
    p = list(input())
    n = int(input())
    l = input()
    if n == 0:
        l = []
    else:
        l = l[1:-2].split(',')

    flag = False
    for j in p:
        if j == 'R':
            l = [l[i] for i in range(len(l)-1, -1, -1)]
        elif j == 'D':
            if len(l) == 0:
                flag = True
                break
            else:
                l.pop(0)

    if flag:
        print('error')
    else:
        print('[' + ','.join(l) + ']')

 

방법 2 - 메모리 40508KB / 시간 3804ms / 코드 길이 705B

 

R이 2번이면 원래 상태로 복귀이기 때문에 이점을 고려한 코드를 구성했다.

 

 

import sys
input = sys.stdin.readline

for i in range(int(input())):
    p = input().rstrip()
    n = int(input())
    l = input().rstrip()[1:-1].split(',')

    if n == 0:
        l = []

    rev = 0
    flag = False

    for j in p:
        if j == 'R':
            rev += 1
        elif j == 'D':
            if len(l) == 0:
                flag = True
                print('error')
                break
            else:
                if rev % 2 == 0:
                    l.pop(0)
                else:
                    l.pop()

    if not flag:
        if rev % 2 == 0:
            print('[' + ','.join(l) + ']')
        else:
            l.reverse()
            print('[' + ','.join(l) + ']')

 

방법 3 - 메모리 40132KB / 시간 164ms / 코드 길이 650B

 

RR을 제거하는 replace를 사용한다.

이후 원 순서일 때 만나는 D와 역순일 때 만나는 D에 따라 f, b를 기억하고 추후 한 번에 계산하는 방법을 사용한다.

이 방법이 훨씬 빠름을 알 수 있다. 

 

import sys
input = sys.stdin.readline

for i in range(int(input())):
    p = input().rstrip()
    n = int(input())
    l = input().rstrip()[1:-1].split(',')
    p = p.replace('RR','')

    if n == 0:
        l = []

    rev, f, b = 0, 0, 0
    flag = False

    for j in p:
        if j == 'R':
            rev += 1
        elif j == 'D':
            if rev % 2 == 0:
                f += 1
            else:
                b += 1

    l = l[f:n-b]

    if f + b > n:
        print('error')
    else:
        if rev % 2 == 0:
            print('[' + ','.join(l) + ']')
        else:
            l.reverse()
            print('[' + ','.join(l) + ']')