백준 5430번 AC 풀러 가기

문제 설명

첫 번째 테스트케이스로 예를 들면,

1. 배열의 순서를 뒤집는다(R) → [4,3,2,1]
2. 첫 번째 수를 버린다(D) → [3,2,1]
3. 첫 번째 수를 버린다(D) → [2,1]

로 연산이 진행되어 최종 결과는 [2,1]이다.

1번째 구현 아이디어

주어진대로 그대로 연산하자.
But, R을 짝수번 연산하는 것은 원래 배열과 결과가 똑같다.
→ 짝수번 연속되어 들어오는 R은 지우자
ex 1) RRRRD = D
ex 2) RRR = R

RRRRDRRDRDRD → RRDRRDRDRD → DRRDRDRD → DDRDRD

전체 코드 - 시간 초과

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    p = list(str(input().rstrip())) # 연산 ['R', 'D', 'D']
    n = int(input()) # 배열 속 수의 개수
    
    # string으로 들어온 입력을 list 형태로 변환
    arr = input().rstrip()
    arr = arr.replace('[', '')
    arr = arr.replace(']', '')
    arr = list(arr.split(','))

    # R이 짝수 번 연속으로 나오는 것을 제거하여 연산 횟수를 줄임
    new_p = []
    i = 0
    while i < len(p):
        if i+1 < len(p) and p[i] == 'R' and p[i+1] == 'R':
            i += 2
        else:
            new_p.append(p[i])
            i += 1

    deq = deque(arr) # D 연산에 덱을 활용
    flag = False
    for elem in new_p:
        if elem == 'R': # R 연산
            deq.reverse()
        else: # D 연산
            if not deq or arr == ['']:
                flag = True
                break
            deq.popleft()
    
    if not flag:
    	# 문자열 형태로 출력해주어야 함
        print('[', end='')
        for i in range(len(deq)):
            if i == len(deq)-1:
                print(deq[i], end=']')
            else:
                print(deq[i], end=',')
        print()
    else:
        print('error')

ValueError ❓

처음에 최종 배열을 출력할 때 print(list(map(int, list(deq))))로 하여 리스트를 그대로 출력했고, ValueError이 나왔다.
리스트를 그대로 출력하면 안되고, 문자열 형태로 출력해주어야 한다.

시간 초과 ❓

• 연산의 최대 횟수는 10만번이고, 수의 최대 갯수도 10만번이다.
• 파이썬 리스트의 remove()의 시간 복잡도는 O(N)
• new_p 리스트를 만들 때 완전탐색 → 연산 횟수를 더 줄여야 함

2번째 구현 아이디어

➡️ R의 개수를 세고 → 홀짝 여부에 따라 popleft(), pop() 중 하나를 한다.
배열 뒤집기는 마지막에 1번만 한다.

전체 코드 - 틀렸습니다

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    p = list(str(input().rstrip()))
    n = int(input())
    # arr를 변환하는 방식을 변경
    arr = input().rstrip()[1:-1].split(',')
    deq = deque(arr)
    flag = False
    rev = 0

    for elem in p:
        if elem == 'R':
            rev += 1 # R의 개수를 count
        elif elem == 'D':
            if len(deq) < 1: # 배열이 비어있는데 D 연산을 진행
                flag = True
                print('error')
                break
            else:
            	# R의 개수에 따라 D 연산 진행
                if rev % 2 == 0:
                    deq.popleft()
                else:
                    deq.pop()

    if not flag:
    	# 처음부터 빈 리스트에 D 연산
        if arr == ['']:
            print('error')
        elif rev % 2 == 0:
            print('[' + ','.join(deq) + ']')
        else:
            deq.reverse()
            print('[' + ','.join(deq) + ']')

틀렸습니다 ❓

• D, 0, [] - error
• R, 0, [] - []

빈 리스트에 R 연산을 하는 것은 가능하다.
하지만 위와 코드와 같은에 if arr == []을 넣으면 R, 0, []일 때도 error라고 출력된다.

그래서 해당 조건문의 위치를 변경해주었다.

전체 코드 - 정답

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    p = list(str(input().rstrip())) # ['R', 'D', 'D']
    n = int(input()) # 4
    arr = input().rstrip()[1:-1].split(',')
    deq = deque(arr)
    flag = False
    rev = 0

    for elem in p:
        if elem == 'R':
            rev += 1
        elif elem == 'D':
            if len(deq) < 1 or arr == ['']:
                flag = True
                print('error')
                break
            else:
                if rev % 2 == 0:
                    deq.popleft()
                else:
                    deq.pop()

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