백준 5430 - AC

Sungwoo Hwang·2021년 3월 20일

백준 알고리즘 코딩테스트

우당탕탕 코테준비

목록 보기

2/6

문제 제목

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

풀이

먼저 이 문제는 특이한 점이 두가지가 있는데, 난이도에(Silver2) 비해서 정답률이 매우 낮고(20%) 관련된 질문이 작성일자 기준으로 9페이지가 넘어간다는 것이다.

백준에서 문제를 풀면서 질문이 많은 문제들은 보통 유명기업 기출문제(아기상어)나 알고리즘 분류별 대표적인 문제들(N-Queen)이 그러한데, 이 문제는 둘다 아니다.

알고리즘의 분류는 구현,자료구조,문자열,덱으로 크게 어려울게 없어 보인다.

문제 설명을 읽고 가장 먼저 주목한 부분은 R 명령어를 실제로 수행 할 필요가 전혀 없다.
또 함수형 언어 AC에 순서를 뒤집는 R 명령어는 있지만 배열의 앞이나 뒤에 원소를 삽입하는 삽입 명령을 의미하는 함수가 없다는 것이다.

첫번째로 왜 R 명령어를 실제로 수행할 필요가 없는지를 보자.
예를 들어서 입력 배열이 [1,2,3,4]일때 RD를 수행하면 배열은 [4,3,2,1]->[3,2,1]이고, 나머지 RD를 마저 수행하면 [1,2,3]->[2,3]이다. R명령어를 만날때마다 직접 배열의 순서를 뒤집어도 되지만, [1,2,3,4]를 기준으로 RD명령어는 결국 마지막 원소인 4를 삭제하라는 함수인것이다. 그 상태에서 RD를 다시 수행하게 되면 첫번째 원소인 1을 삭제하라는 의미다.

다시 말해서 R이 몇번 들어 왔는지, 정확히 말하자면 R이 홀수번 혹은 짝수번 들어 왔는지에 따라서 배열의 맨 앞의 원소를 삭제할지 맨 뒤의 원소를 삭제할지 결정하면 되는것이다.

R이 1,3,5,7... 이렇게 홀수번 들어온 상태라면 맨 뒤의 원소를 삭제하면 되는것이고 2,4,6,8... 이렇게 짝수번 들어온 상태라면 맨 앞의 원소를 삭제하면 되는것이다.

두번째로 삽입 명령이 없다는 점이 중요한 이유는 [1,2,3,4]에 5를 삽입하면 [1,2,3,4,5]가 되지만 [1,2,3,4]에 R을 수행한 후 5를 삽입하면 [4,3,2,1,5]가 되기때문에 배열이 완전히 달라지게 된다.
그 말은 삽입 직전의 배열에 대해서 R명령어를 직접 수행하고 그 결과 배열을 계속 저장해야 하는것이다.
삽입 명령이 없다면 R명령어는 O(1)만큼의 수행시간이 걸리지만(현재 몇번째 R이 들어 왔는지의 상태를 저장해야하니)
삽입 명령이 있다면 R 명령어는 직접 순서를 뒤집는 시간인 O(N)만큼의 시간이 걸리게 된다.

이런 점들 때문에 이 문제는 쉬운편이라고 생각했고, 양방향 삭제가 가능한 deque를 사용해 풀이하기로 했다.

현재 배열이 뒤집어진 상태인지 기록하는 is_set_reverse=False 변수를 만들고, R이 들어오면
True->False, False->True로 바꿔주게끔 했다.
is_set_reverse가 True면 맨 뒤에서 원소를 삭제하고 False면 맨 앞에서 원소를 삭제하는 것으로 구현했다.

또 문제의 조건을 따라 빈 배열에 대해서 D 명령어를 수행하면 error를 출력하게끔 했다.

마지막으로 is_set_reverse상태에 따라서 현재 배열을 순서대로 출력할지, 역순으로 출력할지 판단하게끔 구현했다.

기본 논리는 간단했지만 입력을 받아서 파싱한 후 리스트로 변환하는 부분이 조금 귀찮았다. 아마 더 깔끔한 파싱 방법이 있을것 같다.

풀이코드

from sys import stdin
from collections import deque

T = int(stdin.readline())


def sol():
  task_set = stdin.readline().rstrip('\n')
  n = int(stdin.readline())

  if n == 0:
    throw = stdin.readline()
    for task in task_set:
      # 길이가 0인데 한번이라도 삭제명령어가 온다면 에러출력
      if task == 'D':
        print('error')
        return
    # 명령어중에 단 한번이라도 D가 안나오면 그냥 빈배열 거꾸로 출력
    print('[]')
    return

  # 배열 입력받고 홀수번째 idx에 있는것들만 빼오기
  # 이러면 한자리 숫자 밖에 받지못함
  # numbers = [ int(x) for idx, x in enumerate(stdin.readline().rstrip('\n')) if idx % 2 == 1 ]

  numbers = deque(map(int, stdin.readline().rstrip('\n')[1:-1].split(',')))
  
  # 실제로 reverse를 하게 되면 TLE
  # reverse_numbers = numbers[::-1]

  is_set_reverse = False

  for task in task_set:
    # R 명령어가 들어오면
    if task == 'R':
      is_set_reverse = False if is_set_reverse else True
      # reverse_numbers, numbers = numbers, reverse_numbers

    # D 명령어가 들어오면
    else:
      if len(numbers) == 0:
        print('error')
        return 0

      if is_set_reverse:
        numbers.pop()
      else:
        numbers.popleft()

  if is_set_reverse:
    print('[' + ','.join(map(str, list(numbers)[::-1])) + ']')
  else:
    print('[' + ','.join(map(str, numbers)) + ']')


for _ in range(T):
  sol()