[백준] #5430 AC(python)

수영·2022년 8월 10일

Python3 백준

백준

목록 보기

30/117

📌문제

선영이는 주말에 할 일이 없어서 새로운 언어 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

백준 5430번 문제

💡Idea

문제 그대로 R이 나오면 reverse를 하고 D가 나오면 배열의 첫 번째 수를 삭제하도록 구현을 하면 시간 초과가 발생합니다.

따라서, 아래👇와 같이 몇 가지 규칙을 바탕으로 문제에 접근해야 합니다.

원래 배열의 순서인 경우 D를 실행하면 맨 앞의 수가, 뒤집어진 배열의 순서인 경우 D를 실행하면 맨 뒤의 수가 삭제된다.

R이 짝수이면 원래 순서, 홀수이면 뒤집어진 순서가 최종 결과의 순서이다.

규칙을 바탕으로

배열의 앞과 뒤에서 실제로 요소들을 삭제하면서 최종 배열을 뽑아내는 코드
실제로 요소를 삭제하지 않고, 배열의 시작 index와 끝 index를 조절하며 최종 배열을 뽑아내는 코드
R을 기준으로 함수를 split하여, 함수들을 하나하나 읽지 않고도 한 번에 최종 배열을 뽑아내는 코드

의 세 가지 코드를 소개해드리겠습니다.

(앞의 두 코드는 제가 고민해서 작성한 코드, 세번째 코드는 찾아보았을 때 가장 많이 나오는 코드입니다!😊)

💻코드1

⏰시간 : 276 ms / 메모리 : 41232 KB

from collections import deque
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T): # 테이스케이스 수만큼 반복
    func_list = list(input().strip()) # 함수 리스트
    n = int(input())
    x = deque(input()[1:-2].split(',')) if n > 0 else input()[1:-2] # 숫자 리스트
    r = 1 # reverse 여부, 1이면 원래 순서 / -1이면 뒤집어진 순서
    if len(list(filter(lambda f: f == "D", func_list))) > n:
    	#D의 개수가 리스트의 길이보다 길면 error 출력
        print("error")
        continue
    for func in func_list:
        if func == "R": # R이면 r의 값 변경 
            r *= -1
        elif func == "D": #D면 r의 값에 따라 맞는 위치에서 pop
            x.popleft() if r == 1 else x.pop()
    # 최종 r이 -1이라면 뒤집어진 순서로, 그렇지 않으면 정상 순서로 출력
    print("[" + ",".join(reversed(x) if r == -1 else list(x)) + "]")

📝코드 설명1

리스트의 앞 뒤에서 숫자를 삭제할 수 있는 leftpop과 pop을 사용하기 위해 deque를 사용하였습니다.

입력받은 테스트케이스마다, D의 개수가 입력받는 숫자 리스트의 많으면 바로 error를 출력해주도록 하였습니다.

에러가 발생하지 않는 경우라면, 입력된 함수를 하나씩 확인합니다.
이 때, r 변수가 사용이 됩니다. r 변수는 현재 배열이 뒤집어진 순서인지, 원래의 순서인지를 나타냅니다.

R인 경우에는 순서가 바뀌었으니 r의 값을 바꿔줍니다.
D인 경우에는 r의 값에 따라 앞 혹은 뒤에서 요소를 하나 삭제해줍니다.

그리고 최종적으로 r의 값에 따라서 배열을 원래 순서 혹은 뒤집어진 순서로 출력하면 됩니다.

💻코드2

⏰시간 : 244 ms / 메모리 : 41232 KB

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T): # 테스트 케이스만큼 반복
    func_list = list(input().strip()) # 함수 리스트
    n = int(input())
    x = (input()[1:-2].split(',')) if n > 0 else input()[1:-2] # 숫자 리스트
    r = 1 # reverse 여부, 1이면 원래 순서 / -1이면 뒤집어진 순서
    start = 0 # 배열의 시작 인덱스
    end = n # 배열의 끝 인덱스
    if len(list(filter(lambda f: f == "D", func_list))) > n: 
    	# D의 개수가 숫자 리스트 개수보다 많으면 error 출력
        print("error")
        continue
    for func in func_list:
        if func == "R": r *= -1 # R인 경우 r의 값 변경
        elif func == "D": # D인 경우 r의 값에 따라 start와 end 값 변경
            if r == 1: start += 1 
            elif r == -1: end -= 1
    # 배열은 start 부터 end 까지 슬라이싱 후 r의 값에 따라 최종 배열 출력
    print("[" + ",".join(reversed(x[start:end])
          if r == -1 else x[start:end]) + "]")

📝코드 설명2

코드 1과 거의 유사한 코드입니다.

다만, 함수 D가 나올 때 실제로 pop하지 않고, start와 end의 값만을 조절하였습니다.

그리고 마지막에 start와 end값이 맞추어 슬라이싱한 리스트를 출력합니다.

💻코드3

⏰시간 : 116 ms / 메모리 : 40396 KB

import sys
input = sys.stdin.readline
for _ in range(int(input())):
	# RR은 순서 변화가 없으므로 삭제 후, R을 기준으로 split
    p = [*map(len, input()[:-1].replace('RR', '').split('R'))]
    n = int(input())
    arr = input()[1:-2].split(',') # 숫자 리스트
    left, right = sum(p[::2]), n - sum(p[1::2]) #1
    
    if left <= right: #2
        arr = arr[left:right] if len(p) % 2 else reversed(arr[left:right])
        print(f"[{','.join(arr)}]")
    else:
        print('error')

📝코드 설명3

입력받은 함수에서 연속적으로 RR이 나오는 경우에 결과는 아무 변화 없기 때문에 그대로 삭제해줍니다.

그리고, 나머지 함수들은 R을 기준으로 split해줍니다. 그렇게 되면 그림의 두번째 줄 같은 리스트가 만들어집니다.
(편의상 0개 이상의 D를 그냥 D라고 표기하였습니다.)

#1 : 그렇게 만들어진 p 리스트는 left와 right을 만들어냅니다. left는 R이 실행되기 전이거나 R이 짝수 번으로 실행되어 원래 순서인 경우의 D의 개수이고, 반대로 right는 R이 한 번 이상 홀수 번으로 실행되어 뒤집어진 순서인 경우의 D의 개수를 n에서 빼준 값입니다. (빼준 이유는 뒤에서 삭제되는 경우이기 때문에, 뒤의 요소들을 제외해주기 위해서입니다)

#2 : 만약 left가 right보다 크다면, D의 개수가 리스트의 길이보다 크다는 뜻이므로 error를 출력합니다.
그렇지 않다면 p의 길이를 2로 나눈 나머지에 따라 순서를 결정하여 최종 리스트를 출력해주면 됩니다.
p의 길이가 홀수라면 그림과 같이 D 문자열이 홀수개 존재한다는 뜻이고, R은 홀수번 나왔다는 뜻이므로 순서를 뒤집어서 출력해줍니다.
그렇지 않으면 원래 순서대로 출력해주면 됩니다.