[백준] 5430번 AC

문제 출처

https://www.acmicpc.net/problem/5430

5430번: AC

 

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

1차 풀이

테스트용 및 1차 작성 답안

import sys
input = sys.stdin.readline

T = int(input()) # # of Test Case 받아주고

for _ in range(T):
    function_list = list(input())  #input은 str로 받아지니 list만 씌워도 각 element로 분해, 혹시 모르니 input -> str로 확실히 변환
    list_len = int(input())  # 사실 쓸모없긴한데 주니 일단 받자
    number_list = eval(input())

    for i in function_list:
        print(number_list)
        print(i)
        if i == 'R':
            number_list = list(reversed(number_list))
            print('Im R')
        elif i == 'D':
            print('Im D')
            if len(number_list) == 0:  #list의 empty 판정으로 인한 에러를 bool을 이용하거나 try구문을 이용해도 될 듯
                print("error")
                break
            else:
                number_list.pop(0)
    print(number_list)

 

python에서는 input()을 받았을 때, string type으로 받아지므로 해당 값을 list, 혹은 integer로 명시적 변환

 

eval 함수

python의 built-in 함수이며 정말 편리하지만, 위험한 함수.

대부분의 구분을 분석하여 자동적으로 처리해주는 유연한 함수이지만 그만큼 python 자체적인 해석에 의존함으로

strip과 같은 방식으로 처리하여주는 것이 더 안전하긴 함.

 

 

위 코드는 "시간 초과" 발생

 

시간 초과의 발생 가능성이 있는 항목은

• input
• list를 reverse 하는 과정

등 이 있지만

해당 코드에서는 input 대신 sys.stdin.readline을 사용하였기에 input에서의 시간 초과라고 보기 힘듦.

'list를 reverse 하는 과정'에서 시간 초과가 발생했다면 해당 과정을 최소화 하는 방향으로 다시 짜보자.

 

 

보완 방향

1. RR이 짝수개 나온 경우 원래의 순서 그대로임으로 해당 작업 미 실행

2. function_list의 구문을 해석하여 원래의 number_list에서 양쪽 끝에서 각 x, y개 제거 및 reverse 작업 0회 or 1회 실행

 

순서대로 해보자.

 

1의 방법을 구현하던 도중 iteration을 도는 과정에서 RR의 짝수개를 처리하는 것이 아닌, function_list 자체에 대해 먼저 정리를 해두고 refine된 function_list를 돌리는 것이 더 효율적이라 판단.

 

 

보완코드

def refine_func(fun_list):
    for i in range(len(fun_list)-1):
        if fun_list[i] == 'P':
            continue
        if fun_list[i] != 'R':
            continue
        elif fun_list[i] == 'R':
            if fun_list[i+1] == 'R':
                fun_list[i]='P'
                fun_list[i+1]='P'
                continue
        else:
            print("?")
            

#뒤쪽의 main for-loop내의 코드 변환
for i in function_list:
        if i == 'P':
            continue
        if i == 'R':
            number_list = list(reversed(number_list))
        elif i == 'D':
            if len(number_list) == 0:  #list의 empty 판정으로 인한 에러를 bool을 이용하거나 try구문을 이용해도 될 듯 ?
                print("error")
                break
            else:
                number_list.pop(0)

 

해당 함수는 function_list를 받았을 때, 짝수개의 연속된 R에 대해서는 P로 변환한다.

R자체를 제거하면 좋긴하지만, iteration에서 list의 index를 참조하기에 삭제하는 방향으로는 힘들 것 같았다.

 

다만, 위 보완코드를 사용한 답안 또한 시간 초과

 

 

2번 방법

Reverse를 0번 혹은 1번만 실행하며 list의 좌, 우측에서 각각 몇번 pop 해야하는지 구한 후 실행

 

 

2차 수정 풀이

#최종 5430

import sys
input = sys.stdin.readline

def refine_func(fun_list):
    for i in range(len(fun_list)-1):
        if fun_list[i] == 'P':
            continue
        if fun_list[i] != 'R':
            continue
        elif fun_list[i] == 'R':
            if fun_list[i+1] == 'R':
                fun_list[i]='P'
                fun_list[i+1]='P'
                continue

T = int(input()) # # of Test Case 받아주고

for _ in range(T):
    function_list = list(input())  #input은 str로 받아지니 list만 씌워도 각 element로 분해, 혹시 모르니 input -> str로 확실히 변환
    list_len = int(input())  # 사실 쓸모없긴한데 주니 일단 받자
    number_list = eval(input())

    refine_func(function_list)

    check_li = [0,0]
    reverse_cnt = 0
    del_cnt = 0
    
    for command in function_list:
        if command == 'P':
            continue
        elif command == 'R':
            check_li.reverse()
            reverse_cnt += 1
        elif command == 'D':
            check_li[0] += 1
            del_cnt += 1

    if del_cnt > list_len:
        print("error")
        continue

    if reverse_cnt%2 ==0:
        pass
    elif reverse_cnt%2 ==1:
        check_li.reverse()
        left_del, right_del = check_li[0], check_li[1]
        for _ in range(right_del):
            del number_list[-1]
        for _ in range(left_del):
            del number_list[0]

    print(number_list)

 

이번엔 출력 초과 발생. 또한 16%에서 걸리는 거 보니 해당 test case에 뭐가 있는 듯.