[BOJ] 백준 5430번 AC - Python

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

5430번: AC

문제 설명

 

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다.

배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다.

예를 들어, "RD"를 입력받으면 R을 수행한 후에 D를 바로 이어서 수행하는 함수이다.

설명은 하자면 먼저 배열에 있는 수의 순서를 뒤집고 그 다음 첫 번째 수를 버리는 연산을 수행하면 된다.

 

 

입력

 

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

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

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

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

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

 

 

출력

 

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

 

 

틀린 이유

 

아래는 처음 작성했던 틀린 코드이다.

# R 뒤집기 => 배열에 있는 수의 순서를 뒤집음
# D 버리기 => 첫 번째 수를 버리는 함수, 배열 비어있으면 에러 발생
import sys
t = int(input()) #테스트 케이스 개수

for _ in range(t) :
  p = sys.stdin.readline().rstrip() #수행할 함수
  n = int(input()) #배열에 들어있는 수의 개수
  a = sys.stdin.readline().rstrip()
  if len(a) > 2 :
    aa = list(map(int, a[1:-1].split(',')))
  else : aa = list()
  
  f = True
  for i in p :
    if i == 'R' : aa.reverse()
    elif i == 'D' : 
      if not aa : 
        f = False
        break
      aa.pop(0)
  if f : print(aa)
  else : print('error')

아래 코드에서 어마무시한 시간 초과를 경험했다.

 

여기서 가장 큰 문제는 두 가지가 있다.

1. list 사용

2. R나올 때 마다 reverse() 사용

 

 

제목풀이 방법 & 정답 코드

 

해결을 해보려고 도전하다가 이유를 모르겠어서 질문을 찾아보다 아래 글과 같은 내용을 발견했다.

여기서 봐야할 것은 1번과 2번 설명이다.

https://www.acmicpc.net/board/view/25456

1. R 명령이 들어온다고 진짜로 배열의 모든 원소를 뒤집으면 절대로 안 됩니다. N개의 원소의 순서를 정말로 바꾸면 당연히 그 원소 수만큼 시간이 걸리고, 그걸 최대 10만 번 수행해야 하니 테스트 케이스 1개만으로도 100억번의 연산이 수행됩니다. R 명령의 핵심은 실제로 원소를 뒤집지 않고도 뒤집힌 것과 같은 효과를 내도록 구현하는 것입니다. C++의 std::reverse(), Python의 a[::-1] 역시 사용해서는 안 됩니다.

2. D 명령에 대해서 보통 배열의 맨 앞 원소를 무작정 지워서는 안 됩니다. C++의 vector::erase(), Java의 ArrayList.remove(), Python의 list.pop() 등으로 배열의 첫 번째 원소를 지울 시, 그 뒤에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨오게 되므로, 그 시간 역시 원소의 수에 비례하여 소요됩니다. 라이브러리 함수는 호출만 하면 N개의 원소를 기적같이 O(1)에 처리해주는 마법사가 아닙니다. 저렇게 원소를 당겨오는 작업 없이도 D의 기능을 구현할 수 있어야 합니다.

위의 코드가 초기 코드였지만 여러번 시도를 하면서 R이 두번 연속해서 나오면 replace('RR','')로 RR이면 지워버리도록 하는 코드도 추가했었다.

RR을 찾기 위해 문자열 전체를 비교하는 과정에서도 문자열이 길어지면 어마어마한 시간이 걸린다.

 

그래서 위의 해결법들을 반영해 수정한 코드가 아래 코드이다.

 

먼저 list 대신 deque를 이용해 첫번째 숫자를 지우는 과정에서 드는 연산을 줄였다.

list의 경우 맨 앞에 있는 원소를 삭제하면 O(n) 시간이 걸리는데, deque를 사용하면 O(1)에 가능하다.

그리고 reverse()를 R이 나올 때마다 계속 수행하지 않고, R의 개수를 카운트를 하고, R의 개수를 계산해서 알맞은 위치의 원소를 삭제해주는 방식을 택했다.

그리고 최종 R의 개수를 보고 reverse()를 마지막에 한번만 수행하는 방식으로 바꿔주었다! 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline
t = int(input())

for _ in range(t) :
  p = input().rstrip()
  n = int(input()) 
  aa = deque(input().rstrip()[1:-1].split(','))
  if n == 0 : aa.clear()
  
  r = 0
  f = True
  for i in p :
    if i == 'R' : 
      r += 1
    elif i == 'D' :
      if not aa :
        f = False
        break
      elif r % 2 == 1: aa.pop()
      else : aa.popleft()
  if r % 2 == 1 : aa.reverse()
  print('['+','.join(aa)+']') if f else print('error')