내 맴

[ BAEKJOON ] No. 5430 AC 본문

Algorithm/Baekjoon 문제풀이

[ BAEKJOON ] No. 5430 AC

뺙사우르수 2020. 4. 21. 17:25
728x90

문제 )

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

 

5430번: AC

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다.

www.acmicpc.net

 

[ 풀이 ]

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)

 

728x90