[Python] 백준 5439 - AC

5430_AC

문제

선영이는 할 짓이 없어서 AC라는 언어를 만들었다고 합니다.

 

커도 반 센세인가?

 

정수 배열을 연산하기 위한 언어로, 두 가지 함수가 존재합니다.

R(뒤집기)은 List.reversed()

D(드랍)는 del List[0]입니다.

 

배열이 비어있을 때 D를 사용하면 에러가 발생합니다.

 

함수가 두 개 밖에 없는데 예외도 없이 바로 에러 행입니다.

 

배열의 초기값과 수행 함수가 주어졌을 때, 최종 결과를 구하면 됩니다.

문자열과 국어문제

문제는 극한의 국어 문제입니다. 문제가 무슨 유희왕 몬스터 카드 효과마냥 꼬여있습니다.

 

일단 입력 자체가 괴랄합니다.

1. 첫 번째로 테스트 케이스의 수 T백준 문제에서는 비교적 보기 힘든 방식입니다.
2. 삼성 sw 엑스퍼트 아카데미 문제 출제 형식인데, 하나의 완성된 테스트 케이스가 세트로 여러 개 들어옵니다.
3. 해당 테스트 케이스에 쓰일 함수 p가 문장으로 입력됩니다.
4. 다음으로 테스트 케이스에서 쓰일 초기 배열의 길이 n을 받습니다.
5. 그 다음에 해당 테스트 케이스의 초기 배열을 리스트 형식의 문자열로 입력받습니다.
6. 즉, 문자열을 파싱하여 리스트로 만들거나 eval함수로 바꿔줘야 합니다.

출력은 error 또는 리스트인데, 이 리스트 조차도 문자열로 출력해야 합니다...

골드 5 문제 치고 평균 정답 비율이 20퍼센트라는 괴멸적인 수준을 보이는데, 국어문제라서 그런 걸까요...?

첫 번째 시도, 괴멸적인 실행속도

import sys

input = sys.stdin.readline

for t in range(int(input())):
    func = input()
    l = int(input())
    arr = []
    string = ''

    # 문자열로 받은 리스트를 리스트로 파싱
    for s in input().strip()[1:]:
        if s.isdigit():
            string += s
        else:
            if string != '':
                arr.append(string)
            string = ''

    # 뒤집힌 상태에선 p가 -1이 되어 리스트의 마지막 수를 삭제시킨다
    p = 0
    for f in func:
        if f == 'R':
            if p == 0:
                p = -1
            elif p == -1:
                p = 0
        elif f == 'D':
            if not arr:
                print('error')
                break
            del arr[p]
    else:
        if p == -1:
            arr = arr[::-1]
        # 출력 조건에 맞게 문자열로 변환
        print(f"[{','.join(arr)}]")

ㅋㅋㅋㅋ

비효율적인 방법일 것이라 예상은 했지만, 상상을 초월한 비효율입니다.

시간 초과가 안 난 게 오히려 신기합니다.

리스트 형태 문자열을 eval()로 파싱할 경우

문자열로 받은 리스트 파싱을 eval로 해보면 괜찮지 않을까 싶어 중간 부분을 살짝 바꿔 실행해봤습니다.

eval() 함수는 evaluate(평가하다)의 어원을 갖고 있습니다.

Python이 직접 문자열을 인식하여 식 또는 알맞은 자료형으로 자동으로 파싱해주는 함수입니다.

 

효율 면에서나, 코드 안정성 면에서나 eval() 은 절대 쓰지 말아야 할 함수입니다.
실무에선 절대 절대 쓰면 안 되는 기능 중 하나입니다.

차라리 모든 경우의 입력에 대해 케이스를 만드는 것이
코드를 해석하기도 쉽고, 안정성도 높으며, 코드에 대한 주도권을 프로그래머가 갖는 방법입니다.

이번 코드에서는 알고리즘 문제 풀이이기 때문에 그냥 써본 것일 뿐입니다!

 

사실, 이런 편리한 작업을 해주는 함수가 절대 빠르거나 적은 리소스를 쓸 거라 예상하진 않았습니다...

arr = list(map(str, eval(input())))

 

진짜 더럽게 느리고 많은 메모리를 잡아먹습니다.

 

당연히 예상은 했으나, 정말 어마어마한 리소스를 잡아먹는 함수였습니다.

문자열을 받는 것은 유지하고, 다른 부분을 줄여보기로 했습니다.

세 번째 시도, 실행 수 줄이기

문제의 조건에서, 실행되는 함수(p)는 최대 100,000개입니다.

그런데 최종 출력에서 중요한 건,

1. 앞 또는 뒤에서 얼마나 삭제했는가?
2. 최종적으로 뒤집혔는가?
3. error가 발생했는가?

이 세 가지입니다.

결국 R은 실행된 시점과 실행 횟수가 짝수인지 홀수인지 파악만 하면 끝입니다.

특히, R이 연속으로 두 번 반복되면 결과에 아무런 영향을 끼치지 않는습니다!

p = DRDDRRDRDD

 

RR은 replace('RR', ' ')로 없애면 됩니다.

p = DRDDDRDD

 

이제 첫 번째 R을 기준으로 좌측에 남은 D의 수는 리스트의 앞에서 삭제할 객체의 수를,

우측에 남은 D의 수는 리스트의 뒤에서 삭제할 수를 나타냅니다.

 

split(p)을 통해 만들어진 리스트의 짝수 인덱스 객체의 길이의 합이 곧 앞에서 삭제될 개수,

홀수 인덱스 객체의 길이의 합이 뒤에서 삭제될 개수가 되는 것입니다.

p = ['D', 'DDD', 'DD']

 

위의 경우에서는 앞에서 3개의 인자, 뒤에서 3개의 인자를 삭제하면 됩니다.

그리고 p의 길이가 홀수면 두 번의 R이 실행된 것이니 그대로 출력하고,

짝수면 최종결과를 뒤집어 출력하면 됩니다.

만약 이 길이들의 합이 배열 길이 n을 넘는 경우, error를 뱉어내면 끝입니다.

정답 코드

import sys

input = sys.stdin.readline

for t in range(int(input())):
    func = input().strip().replace('RR','').split('R')
    rev = 0
    if len(func)%2 == 0:
        rev = 1

    l = int(input())
    arr = []
    arr_string = input().strip()
    string = ''
    if l:
        arr = arr_string[1:-1].split(',')
    p, r = 0, 0
    for i in range(len(func)):
        if i%2 == 0:
            p += len(func[i])
        else:
            r += len(func[i])
        if p+r > l:
            print('error')
            break

    else:
        if r:
            arr = arr[p: -r]
        else:
            arr = arr[p:]
        if rev:
            arr.reverse()
        print(f"[{','.join(arr)}]")

 

실행 결과는 다음과 같습니다.

메모리	시간	코드길이
39624KB	116ms	697B