[백준/Python] 덱 - AC(5430)

AC

---

 

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

---

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

---

입력 예시

4 RDD 4 [1,2,3,4] DD 1 [42] RRD 6 [1,1,2,3,5,8] D 0 []

 

---

출력 예시

[2,1] error [1,2,3,5,8] error

 

---

나의 풀이

import sys
from collections import deque

T = int(sys.stdin.readline()) # 테스트케이스 개수

for _ in range(T):
    p = sys.stdin.readline().rstrip() # 수행할 함수
    n = int(sys.stdin.readline()) # 배열에 들어있는 수의 개수

    # 배열 ([1,2,3,4]를 입력으로 받은 것을 리스트에 1, 2, 3, 4로 저장하기)
    arr = list(sys.stdin.readline().rstrip().split(','))
    arr[0] = arr[0][1:]
    arr[n-1] = arr[n-1][:len(arr[n-1])-1]

    # 리스트 형식의 arr을 덱 형식으로 변경
    arr = deque(arr)

    r = 1 # 뒤집기 여부 (r=1이면 앞부터, r=-1이면 뒤부터)
    error = 0 # error 발생 여부

    # p 하나씩 수행
    for fun in p:
        if fun == 'R':
            r = -r # r=1이면 앞부터(popleft), r=-1이면 뒤부터(pop)
        elif fun == 'D':
            # 배열이 비어있을때 D를 사용하면 에러
            if len(arr) == 0 or arr[0] == '':
                error = 1
                break

            # r=1이면 앞부터(popleft), r=-1이면 뒤부터(pop)
            if r == 1:
                arr.popleft()
            else:
                arr.pop()

    # r = -1이면 뒤집어서 출력
    if r == -1:
        arr.reverse()
    
    if error == 1: # error 발생했으면 error 출력
        print('error')
    else: # 리스트 형식으로 출력 ex)[1,2]
        print('[', end='')
        print(*arr, sep=',', end=']\n')

- 💡 아이디어
p 내의 함수가 100,000개까지 존재할 수 있지만 시간은 1초이므로, 빠르게 동작하는 덱을 사용했다. 함수가 R이라면 뒤집기를 수행해야하지만, R이 나올 때마다 reverse()를 수행하면 시간이 걸리므로, popleft와 pop만 이용하도록 하였다. r=1로 두고, R이 나오면 r에 (-1)을 곱하여, r이 1이면 앞부분을 제거하는 pop()을 이용하고, r이 -1이면 뒷부분을 제거하는 popleft()를 이용하도록 하였다.

마지막 부분에서만 r이 -1이라면 reverse()를 하여 뒤에서부터 출력하도록 하였다.

 

- 📚 후기

뒤이어 쓸 것이지만, 이 코드는 세번째 시도한 코드이다. 두번의 코드는 시간초과가 떴다. 처음 코드에서는 덱을 이용하였지만 R이 등장할 때마다 계속 reverse를 수행하여 시간초과가 떴고, 두번째 코드에서는 덱을 사용하지 않고, 리스트를 사용하여 시간초과가 떴다.

 

- ✏️ 배운점

시간이 부족하다면 덱의 pop, popleft, append, appendleft로만 이용하여 문제를 해결할 수 있는지 생각해보자!

 

# 시간초과가 뜬 첫번째 코드(실패한 코드)

import sys
from collections import deque

T = int(sys.stdin.readline())

for _ in range(T):
    p = sys.stdin.readline().rstrip() # 수행할 함수
    n = int(sys.stdin.readline()) # 배열에 들어있는 수의 개수

    # 배열 ([1,2,3,4]를 입력으로 받은 것을 리스트에 1, 2, 3, 4로 저장하기)
    arr = list(sys.stdin.readline().rstrip().split(','))
    arr[0] = arr[0][1:]
    arr[n-1] = arr[n-1][:len(arr[n-1])-1]

    # 리스트 형식의 arr을 덱 형식으로 변경
    arr = deque(arr)
    
    error = 0 # error 발생 여부
    for i in range(len(p)):
        if p[i:].count('D') > len(arr): # D의 개수가 배열 요소의 개수보다 많다면 error 발생
            error = 1
            break

        if p[i] == 'R': # 함수가 R이라면 reverse
            arr.reverse()
        
        if p[i] == 'D': # 함수가 D라면 제거
            if len(arr) == 0 or arr[0] == '': # 배열이 비어있을때 D를 사용하면 에러
                error = 1
                break
            else:
                arr.popleft()
    
    if error == 1: # error 발생했으면 error 출력
        print('error')
    else: # 리스트 형식으로 출력 ex)[1,2]
        print('[', end='')
        print(*arr, sep=',', end=']\n')

# 시간초과가 뜬 두번째 코드(실패한 코드)

import sys
from collections import deque

T = int(sys.stdin.readline())

for _ in range(T):
    p = sys.stdin.readline().rstrip() # 수행할 함수
    n = int(sys.stdin.readline()) # 배열에 들어있는 수의 개수

    # 배열 ([1,2,3,4]를 입력으로 받은 것을 리스트에 1, 2, 3, 4로 저장하기)
    arr = list(sys.stdin.readline().rstrip().split(','))
    arr[0] = arr[0][1:]
    arr[n-1] = arr[n-1][:len(arr[n-1])-1]

    # 리스트 형식의 arr을 덱 형식으로 변경
    arr = deque(arr)

    error = 0 # error 발생 여부
    stop = 0
    
    while True:
        #print(i)
        if p[0:].count('D') > len(arr) or arr[0] == '': # D의 개수가 배열 요소의 개수보다 많다면 error 발생
             error = 1
             break
             
        # 연속된 R 혹은 연속된 D 개수 세기 
        # (ex. p가 RRDDD라면 R의 연속 개수 2를 세고 RR삭제, p는 DDD가 됨. 이 후 D의 연속 개수 3 세고 DDD삭제)
        cnt = 1
        order = p[0]
        if order == 'R': # 함수가 R이라면
            j = p.find('D') # p 내의 D 중 가장 앞의 index를 구함
        else: # 함수가 D라면
            j = p.find('R') # p 내의 R 중 가장 앞의 index를 구함
            
        if j == -1: # 함수가 R일 때 p 내에 D, 함수가 D일 때 p 내에 R이 없다면
            cnt = len(p) # cnt는 남은 p의 개수
            stop = 1 # p를 전부 본 것이므로 멈추기
        else:
            cnt = j 
            p = p[j:] # 개수를 센 함수는 삭제
        
        if order == 'R': # 함수가 R이라면
            if cnt % 2 == 1: # R의 개수가 홀수일 때만 뒤집기
                arr.reverse()
        else: # 함수가 D라면
            arr = arr[cnt:] # arr의 D의 개수만큼 앞부분 삭제
        
        if stop == 1: # p를 전부 봤다면 멈추기
            break    
            
    if error == 1: # error 발생했으면 error 출력
        print('error')
    else: # 리스트 형식으로 출력 ex)[1,2]
        print('[', end='')
        print(*arr, sep=',', end=']\n')