[골드 V] 5430번. AC

 문제 

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

5430번: AC

 사용 언어 

Python3

 풀이 과정 

오랜만의  골드  문제!!

 

처음 내가 짰던 코드는 다음과 같다. 나름 붙어있는 RR은 원래대로 돌아오기 때문에 없애는 처리를 했는데도 시간초과가 났다..! 심지어 pypy3로도...

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

def func (functions, array):
    for func in functions:
        if func == "R":
            array = deque(reversed(array))
        elif func == "D":
            if len(array) == 0:
                return "error"
            array.popleft()
    return array

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        functions = input().strip().replace("RR", "")
        n = int(input())
        array = deque(input().strip()[1:-1].split(","))
        if n == 0:
            array = deque([])
        result = func(functions, array)
        if result != "error":
            result = "[" + ",".join(result) + "]"
        print(result)

함수의 길이가 100,000개까지 가능한데 아무리 RR을 없는 취급해도 실행이 안 될만 했다..ㅎㅎ

 

골드 I도 아니고 골드 V라서 오기 생겨서 다른 방법 생각해내가지고 끝까지 풀었더니... (시간은 진짜 오래 걸렸지만) 결국 맞았습니다!!

내가 생각해 낸 다른 방법이란 전체 R의 개수가 홀수인지 짝수인지 구분해서 각각 방향에서 제거해야 할 개수를 세고, 최종적으로 홀수일 경우에만 한 번 뒤집어주는 것이었다.

 

그리고 아래 다른 사람 풀이를 보고 출력 방식을 변경해 8ms 더 줄이는 데 성공했다.

 

지금 생각해보면 처음부터 이렇게 푸는 문제였나보다... 자꾸 습관처럼 문제가 설명한 행위(?)를 진짜 그대로 구현하려고 하는데, 사람의 머리로 연산 과정을 줄일 수 있다면 줄여야 한다는 걸 명심하자.

 

 제출 답안 

from sys import stdin
input = stdin.readline

def func (functions, array):
    r, ld, rd = 0, 0, 0
    for func in functions:
        if func == "R":
            r += 1
        elif func == "D":
            if r % 2 == 0:
                ld += 1
            else:
                rd += 1

    if len(array) < ld + rd:
        return "error"
    else:
        if r % 2 == 1:
            array = array[::-1]
            result = array[rd:len(array)-ld]
            answer = ",".join(result)
        else:
            result = array[ld:len(array)-rd]
            answer = ",".join(result)
        return "[" + answer + "]"
        
if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        functions = input().strip().replace("RR", "")
        n = int(input())
        array = input().strip()[1:-1].split(",")
        if n == 0:
            array = []
        print(func(functions, array))

 

 다른 사람 풀이 

진짜 깔끔하다... 이거 보고 format string 사용하면 좀 더 줄어들까싶어 나도 변경해보았는데 역시.. 테스트케이스가 많은 = 출력이 많은 문제라 그런지 8ms가 줄어들었다!!

from sys import stdin
input = stdin.readline

def solve():

    for _ in range(int(input())):
        # 'RR' 는 안뒤집는 것과 동일하므로 ''로 바꿔준다
        p = [*map(len, input()[:-1].replace('RR', '').split('R'))]

        n = int(input())
        arr = input()[1:-2].split(',')
        # [left, right) 가 출력된다
        left, right = sum(p[::2]), n - sum(p[1::2])

        if left <= right:
            # len(p) % 2 == 1 인 경우 왼쪽에서 오른쪽 방향
            arr = arr[left:right] if len(p) % 2 else reversed(arr[left:right])
            print(f"[{','.join(arr)}]")
        else:
            print('error')

if __name__ == '__main__':
    solve()

그나저나 혼자만 108ms로 1위... 부럽다 짜릿하겠다🥴