[ BAEKJOON ] No. 5430 AC

문제 )

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

5430번: AC

 

[ 풀이 ]

AC연산에 대한 알고리즘을 설명하기 전에 이 문제는 입력과 출력의 형식이 정해져있기 때문에 입력과 출력 방식에도 신경을 써줘야한다. 

- 입력

처음에 [x1,...,xn]과 같은 형태로 배열에 들어있는 수를 입력해야하므로 eval함수를 사용하였다

✔ eval()
- Python의 내장 함수.
- 문자열도 표현된 식을 인수로 받아 컴파일 코드로 변환한다. 

-  eval()의 예시

#1
x=100
print(eval('x+200'))
# result= 300

#2
l=eval('[1,2,3,4]')
print(l)
# result=[1, 2, 3, 4]

 

 

- 출력

출력의 경우 문제를 풀 때 deque을 이용하여 문제를 풀었는데 그냥 list출력하듯 출력하면 

q=deque([1,2,3,4])
print(q)
# result=deque([1, 2, 3, 4])

이런식으로 출력될 때, 값이 deque에 감싸져서 나온다. 
고로 이 안의 값들을 차례로 출력해줘야하는데 join을 이용하여 deque안의 값들을 출력하였다. 

 

★ ERROR !

deque안의 값이 int값들인데, join함수는 string값들만 사용 가능하므로 그냥 join만 하면 에러가 난다.

구글링 해보니, 

print(",".join(map(str,dq)),end="")

이러한 방법으로 map을 사용하여 deque안의 값을 int에서 str로 변환해주면 된다. 

 

 

- AC연산에 대한 Algorithm 

문제가 요구하는 사항들을 popleft()와 reverse()를 이용해서 곧이곧대로 AC연산에 대한 알고리즘 짜보았는데 시간초과가 되어버렸다. 

< 원래 짰던 코드 >

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

def AC(p,queue):
    for i in p:
        if i=='D':
            if not queue:
                return -1
            else:
                queue.popleft()
        elif i=="R": #R
            queue.reverse()
    return queue


T=int(input())
for i in range(T):
    p=list(input())
    n=int(input())
    queue=deque(eval(input()))
    answer=AC(p,queue)
    if answer==-1:
        print("error")
    else:
        print("[",end="")
        print(",".join(map(str,queue)),end="")
        print("]")

 

그래서 구글링을 이리저리 해보고나서 코딩을 다시 해보았더니 문제를 해결할 수 있었다. 

< AC연산 Algorithm의 흐름 >

✔ r (초기값=false)   → reverse의 상태에 대해 알려주는 변수 
          If r=false인 경우 ) reverse되지 않은 상태
                                             pop해야하는 경우 앞 원소를 제거해야한다. 
          else r=true인 경우) reverse된 상태
                                                pop해야하는 경우 reverse된 list의 앞 원소를 제거해야 하므로                                                                                                     reverse되지 않은 list에서는 뒤의 원소를 제거 해야한다   
✔ d (초기값=false)
          If d=true인 경우 ) 더이상 pop할 원소가 없는 경우 →  후에 error 출력 해야한다
✔ p → 명령어 모아놓은 list

1. 명령어 list인 p의 원소들에 하나씩 접근한다 → i
         if 명령어(i)가 'R'인 경우,
                 Ⅰ. r=true로 바꿔준다
         else 명령어(i)가 'D'인 경우,
                 if deque가 비어있는 경우
                               Ⅰ. d=true로 바꿔주고 break해주기
   if r=True인 경우,  (deque가 reverse되어있는 상태 의미)
                               Ⅰ. pop해주기
                 else r=False인 경우, (deque가 reverse되어있지 않은 상태 의미)
                               Ⅰ. popleft해주기 

2. 
if d=true인 경우  → error출력
else d=false인 경우,
         2-1)
         if r=true인 경우 (reverse되어있는 상태),
                 Ⅰ. deque를 reverse해주기
         2-2)
         deque를 print해주기 

 

- python code

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

def AC(p,dq):
    r=False
    d=False
    for i in p:
        if i=="R":
            r=not r # r=true
        elif i=="D":
            if not dq: # deque가 비어있는 경우
                d=True
                break
            if r: # True인 경우 (뒤에서 원소 삭제)
                dq.pop()
            else: # False인 경우 (앞에서 원소 삭제)
                dq.popleft()
    if d:
        print("error")
    else:
        if r: # r=true인 경우 -> reverse해주기
            dq.reverse()
        #deque를 print해주기 
        print("[",end="")
        print(",".join(map(str,dq)),end="")
        print("]")


# Data input
T=int(input())
for i in range(T):
    p=list(input())
    n=int(input())
    dq=deque(eval(input()))
    AC(p,dq)