[백준 #5430] AC

1. 문제 설명

2. 해설

얼핏 보면 시키는 대로 구현하면 되지 않나 싶지만 시간 제한이 1초기 때문에 효율성을 생각해서 풀어야 한다. 역순 정렬을 하는 데 O(n)의 시간복잡도가 소요되고, list.pop(0) 연산에도 마찬가지로 지우고 한 칸씩 앞으로 당기기 때문에 O(n)의 시간이 소요된다. 그리고 이걸 명령어의 개수만큼 반복하기 때문에 총 O(n^2) 시간이 소요되는데, 이러면 당연히 시간 초과다.

우선 'R'은 배열을 뒤집는 함수니까 R이 2번 들어오면 뒤집는 의미가 없으므로 없애주고, rev라는 플래그를 하나 만들어서 뒤집은 상태일 때 True, 아닐 때 False로 두자. 그리고, 삭제 연산을 할때 rev에 따라 인덱스를 앞으로 밀거나 뒤에서 하나 당기는 식으로 삭제 처리를 해 주면 된다. 출력을 할 때는 앞과 뒤를 가리키는 index의 합이 n보다 같거나 작아야만 올바른 출력이 되고, 아닐 때는 error를 return해주면 끝.

3. 코드

from sys import stdin
input = stdin.readline

def solution(cmds, nums, n):
    cmds.replace('RR', '') #뒤집기를 두 번 하면 뒤집지 않는 것과 같음
    s, e, rev = 0, 0, False
    for cmd in cmds:
        if cmd == 'R':
            rev = not rev
        elif cmd == 'D':
            if not rev: #역순정렬이 아닐 경우
                s += 1
            else:
                e += 1
        
    if s+e <= n:
        res = nums[s:n - e]
        if not rev:
            return '['+','.join(res)+']'
        else:
            return '['+','.join(res[::-1])+']'
    else:
        return 'error'

T = int(input())
for _ in range(T):
    cmds = input()
    n = int(input())
    nums = input().rstrip()[1:-1].split(',')
    if n==0: []
    ans = solution(cmds, nums, n)
    print(ans)

4.여담

최근 프로그래머스만 풀다가 오랜만에 백준 문제를 푸는데, 백준이 입출력 형식을 깐깐하게 봐서 조금 귀찮은 느낌이다. 그리고 외부 IDE를 필수적으로 사용해야 한다는 것도? 아무튼 그런 걸 개선한다면 백준도 충분히 좋을 텐데...