[백준] 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를 출력한다.

 

📚 문제 해석

주어진 명령대로 문자열을 뒤집거나 인덱스 0의 문자를 지우면 되는 문제였다. 첫 제출에는 시간초과 판정을 받았다. 이유는 reverse() 함수를 사용하였기 때문이다. 한두번 사용한다면 모를까 입력으로 100000 자리의 문자열을 100000번 reverse 하라고 하면 시간초과 나는 것은 당연지사이다.
 
잠깐 고민해보았더니 reverse 함수를 사용하지 않고 문자를 뒤집을 방법이 떠올랐다. 우선 입력으로 R이 여러번 들어온다고 하여도 최종적으로는 한번 뒤집거나 뒤집이 않을 것이다. 즉 R이 짝수번 입력된다면 뒤집지 않아도 되고, 홀수번 들어온다면 한번만 뒤집으면 된다. 그리고 list[-1]를 사용하여 문자를 뒤집어 주었다.(그게그건가?ㅎ, 그렇다하여도 2번 이상 reverse 함수를 사용하지 않는다.)

그리고 문자열을 지우는 것도 매번 초기화 해줄 필요없이, 왼쪽에 지울 문자랑 오른쪽에 지울 문자 체크하여 마지막에 출력할 때 그부분 제외하고 출력해주면 시간을 훨씬 줄일 수 있었다. list[left:n-right]

 

알고리즘 분류에는 덱도 포함되어 있었지만 deque 불러오지 않고도 해결할 수 있었다. (뿌듯(?))

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    code = input().rstrip() # 명령어
    n = int(input()) # 문자열 개수
    nums = list(map(str,input().rstrip().split(','))) # 문자열 , 으로 분리
    rev = 0 # 리버스 체크 변수
    left = 0 # 왼쪽 삭제 변수
    right = 0 # 오른쪽 삭제 변수
    for i in code: 
        if i == 'R': # 한번 뒤집으래! 응 안뒤집어~
            rev += 1
        else: # D 입력시
            if rev%2==0: # 현재 뒤집히지 않은 상태라면 왼쪽거 제거할 거임
                left += 1
            else:
                right += 1 # 뒤집힌 상태 오른쪽거 제거할 거임
        if n < (left + right): # 문자수보다 지우는 것이 더 많을 때 error 
            print("error")
            break
    else: # for else 문이다. 
        nums[0] = nums[0].replace('[','') # 제일 앞의 문자 [ 제거해줌
        nums[-1] = nums[-1].replace(']','') # ] 이것도 제거해줌
        if rev%2 == 0: # 안뒤집어도 된다면
            print('['+','.join(nums[left:n-right])+']') # 이쁘게 출력해줌
        else: # 뒤집어야 한다면
            print('['+','.join(nums[left:n-right][::-1])+']') # 아름답게 출력해줌
            # 띄어쓰기 주의! 하면 안됨ㅎ

 

🍭 시행착오

 

🔗 문제링크 AC

5430번: AC