[python] 백준 5430 - AC

게시 2024/01/19 업데이트 2024/02/26

By Inmo-Jeong 8 분읽는 시간

백준 5439 - AC [GOLD 5]

5430_AC

문제

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

커도 반 센세인가?

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

R(뒤집기)는 List.reversed(), D(드랍)은 del List[0]이다.

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

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

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

문자열과 국어문제

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

일단 입력 자체가 괴랄하다.

첫 번째로 테스트 케이스의 수 T 온다.
삼성 sw 아카데미 문제 출제 형식인데, 하나의 완성된 테스트 케이스가 세트로 여러 개 들어온다.
백준 문제에서는 보기 힘든 방식이다.
해당 테스트 케이스에 쓰일 함수 p가 문장으로 입력된다.
다음으로 테스트 케이스에서 쓰일 초기 배열의 길이 n을 받는다.
그 다음에 해당 테스트 케이스의 초기 배열을 리스트 형식의 문자열로 입력받는다.
즉, 문자열을 파싱하여 리스트로 만들거나 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이 직접 문자열을 인식하여 식 또는 알맞은 자료형으로 자동으로 파싱해주는 함수다.

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

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

ㅋㅋㅋㅋㅋ아니 그냥 오답처리 하라고 ㅋㅋㅋㅋㅋㅋ

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

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

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

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

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

앞 또는 뒤에서 얼마나 삭제했는가?
최종적으로 뒤집혔는가?
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

python, 알고리즘