[백준] 5430번 AC, 파이썬 문제 풀이

문제

백준 5430번, AC 문제를 해결했습니다. 배열을 뒤집거나 첫 번째 원소를 제거하는 함수를 구현하는 문제입니다.

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

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를 출력한다.

 

▲ 5430번 AC 예시

 

 

문제 풀이

처음 문제를 풀 때는, 문제에 나와있는 그대로 풀었습니다. R, D 함수를 구현해 호출하는 형식으로 풀었습니다. 테스트 케이스가 100개까지 들어올 수 있는 문제이기 때문에, 당연히 시간 초과가 발생할 것이라고 생각했습니다. 알면서도, 내심 큰 연산이 아니기 때문에 괜찮지 않을까..? 하는 마음도 있었던 것 같습니다. 당연히 결과는 시간 초과가 발생했습니다.

 

함수를 직접 작성해보니, 가장 시간을 많이 잡아먹는 것은 당연히 R 함수입니다. 평균적으로 O(NlogN)의 시간이 걸리기 때문인데, R 함수가 들어올 때마다 R 함수를 진행하면 끝도 없습니다. 조금 생각해보면, R을 2번 하면 안한 것과 똑같은 것을 알 수 있습니다. 그래서, 처음 함수(p)가 입력되면 R의 개수를 세려고 했습니다. 반복문을 통해서 작성을 해보니, 마음에 들지 않았습니다. 함수의 길이는 최대 10만인데, 최소 10만번의 연산을 더 해야하기 때문입니다.

 

그래서, 연산을 진행할 때 R 함수의 숫자를 세는 것입니다. R의 개수가 짝수이면 뒤집지 않아도 되고, R의 개수가 홀수이면 뒤집어야합니다. 이제 D함수를 생각해야 합니다. 첫 번째 원소를 제거하는 함수입니다. 앞서 나온 R함수의 수가 홀수이면, 맨 뒤 원소를 제거해야 합니다.

 

마지막 출력할 때만 R함수를 실행해 정수 배열을 뒤집어서 출력하고, 그 전까진 D함수 앞에 나온 R함수의 개수를 통해서 원소를 제거합니다.

이를 코드로 확인하면 다음과 같습니다.

TC = int(input())

for _ in range(TC):
    func = input()
    N = int(input())
    
    lock=0
    cnt=0

    num = input().split(",")
    num[0]=num[0].strip("[")
    num[len(num)-1] = num[len(num)-1].strip("]")
    
    if(N==0):
        for m in func:
            if(m=='D' and len(num[0])==0):
                print("error")
                lock=1
                break
    else:
        num = list(map(int, num))
    
    if (lock==0):
        for i in func:
            if(i=='R'):
                cnt+=1
            elif(i=='D'):
                if(len(num)==0):
                    lock=1
                    print("error")
                    break
                elif(cnt%2==1):
                    num.pop()
                else:
                    num.pop(0)
            else:
                lock=1
                print("error")
                break
        
    if(lock==0):
        if(cnt%2==1):
            num.reverse()
        print("[",end="")
        
        idx=0
        while(idx<len(num)):
            print(num[idx],end="")
            if(idx==len(num)-1):
                break
            print(",",end="")
            idx+=1
        print("]")
    else:
        continue

항상 반례를 찾는 것이 가장 큰 고역인 것 같습니다. 이번에도 배열의 수 n이 0개 일 때 R을 하게 되면 당연히 에러라고 생각했는데, 빈 배열을 뒤집어도 빈 배열이니 그대로 출력하는 것이 답이었습니다. 사실, 문제에는 빈 배열에 R함수를 넣어도 에러란 말이 없었음에도 불구하고 혼자 단정짓는 것이 문제인 것 같습니다.

 

정리

실행 시간이 4152ms로 제가 푼 문제 중에 큰 편입니다. 더 효율적인 방법을 찾고자 다른 분들의 풀이를 확인했습니다. 대부분 Deque를 활용해서 문제를 해결했습니다. deque의 leftpop()과 pop()을 활용해서 해결했는데, 저는 리스트의 pop()함수만을 활용해서 문제를 해결했습니다. 

다른 분이 실행 시간을 줄이려고 코드를 수정하신 것을 봤습니다. D가 나올 때마다 pop() 하지 않고, 갯수를 기억했다가 마지막에 한 번에 하는 것입니다. pop(0)을 하게 되면, 앞에 것을 지우고 한 칸씩 당겨야 돼서 O(N)의 시간이 필요합니다. 다음 블로그에서 참고했습니다.

https://chancoding.tistory.com/41

[Python] 백준 5430번 AC - 효율적인 알고리즘 3720ms에서 132ms