[Python] 백준 5430번 AC 문제 리팩토링

백준 5430번 AC 문제를 풀던 중, 시간 초과와 IndexError 등을 해결하는 과정에서 다른 분들의 코드를 참고하게 되었고, 내가 작성한 코드보다 문제를 간결하고 효율적으로 처리할 수 있는 방법들에 대해 배울 수 있었다. 이에 코드 리팩토링겸 기록하는 차원에서 작성해보는 포스팅이다.

1. 문자열에서 숫자를 추출하는 방법

문제에서 배열이 '[x1,...,xn]'과 같은 형태로 주어지는데 기존에는 대괄호와 쉼표를 걸러내고자 isdigit()으로 각 문자가 숫자인지 아닌지 판별하였다. 이때 배열 안에 두 자릿수가 존재할 수 있으므로 빈 문자열을 가지는 변수 tmp를 두어 숫자가 아닌 문자가 나올 때까지 이에 누적하는 방식으로 접근했다.

tmp = ''
for i in a:
    if i.isdigit():
        tmp += i
    else:
        if tmp:
            queue.append(tmp)
            tmp = ''

Python에서 문자열은 immutable 하기 때문에 문자열간 '+=' 연산 사용시 기존 문자열을 복사하고, 복사한 문자열에 이어 붙이는 방식으로 동작하여 시간 초과가 발생할 수 있다. '+=' 연산을 사용하지 않으면서 동시에 보다 간결한 코드로 바꿀 수 있는 방법은 모든 문제에서 거의 빠짐없이 사용되는 split()을 활용하는 것이다. '[x1,...,xn]'에서 array[1:-1]로 맨 앞과 맨 뒤에 위치한 대괄호를 없애면 split(',')으로 숫자만을 추출할 수 있게 된다.

단, array[1:-1].split(',')이 빈 문자열('')을 원소로 가지는 리스트인 경우, D 함수를 실행하면 error를, 그렇지 않으면 ['']를 출력해야 하므로 원소가 빈 문자열인지 확인하는 로직을 추가해주어야 한다.

parsed = array[1:-1].split(',')
queue = deque(parsed) if parsed[0].isdigit() else deque()

2. 문제의 핵심이었던 배열을 뒤집는 방법

문제에서 함수는 최대 10만 개 존재할 수 있고, 배열의 최대 길이는 10만이다. 따라서 R 연산(뒤집는 연산)이 최대 100억 번 실행될 수 있기 때문에 O(n)의 시간 복잡도를 가지는 reverse()를 사용하는 것은 시간 초과를 초래할 수 밖에 없다. 통상적으로 시간 복잡도가 O(n)인 경우, n의 허용 범위는 10,000,000까지이다.

따라서 실제로 뒤집지 않고도 뒤집은 것과 같은 효과를 낼 수 있는 방법이 필요했고 처음으로 떠올린 방법은 start_index, end_index 변수를 두는 것이었다. R 연산에 대해서는 start_index와 end_index를 서로 바꿔주고 D 연산에 대해서는 뒤집힌 여부에 따라 맨 앞의 위치를 하나씩 당겨주는 방식으로 구현했다.

start_index = 0
end_index = n - 1

for command in p:
    if command == 'R':
        start_index, end_index = end_index, start_index
    else:
        if queue:
            if start_index < end_index:
                end_index -= 1
                    
                queue.popleft()
            else:
                start_index -= 1
                    
                queue.pop()
        else:
            is_valid = False

아이디어 자체에는 문제가 없었지만 start_index와 end_index 따로, queue 따로 연산을 적용하지 않고도 처리할 수 있는 방법을 찾게 되어 아래와 같이 변경하였다. 바로 is_reversed를 놓고 상태를 변경하는 방식이다.

if queue:
    if is_reversed:
        queue.pop()
    else:
        queue.popleft()
else:
    is_valid = False
    break

3. ','을 포함하여 효과적으로 출력하는 방법

[x1, ..., xn]과 같은 형태로 출력하는 문제라면 queue의 원소를 int로 맵핑하여 그대로 출력하면 되지만 [x1,...,xn] 형태로 출력해야 하기 때문에 이에 맞는 적절한 출력 방법이 필요했다.

앞서 start_index와 end_index를 두고 풀었기 때문에 출력할 때 이를 비교하여 뒤집힌 상태인지를 우선적으로 판단하였다. 뒤집힌 여부에 따라 for 문을 돌면서 출력하였으며 이때 마지막 원소가 아닌 경우에는 ','를 붙이는 방식으로 출력 포맷을 맞춰주었다.

print('[', end='')
        
if start_index < end_index:
    for i in range(start_index, end_index + 1):
        if i == end_index:
            print(queue[i], end='')
        else:
            print(queue[i], end=',')
else:
    for i in range(start_index, end_index - 1, -1):
        if i == end_index:
            print(queue[i], end='')
        else:
            print(queue[i], end=',')
        
print(']')

다른 분들 코드를 보면서 가장 아차싶었던 부분인데 is_reversed 변수를 사용하는 동시에 join()을 사용하면 위 코드를 아래와 같이 획기적으로 줄일 수 있다.

한동안 join()을 사용할 일이 없었더니 그새 까먹었다. 그동안은 ''.join()과 같은 형태로 사용하여 문자열로 만드는 데 사용했기 때문에 ','를 중간 중간에 넣어 합치는 데에는 떠오르지 않았던 것 같기도 하다.

print('[', end='')
        
if is_reversed:
    queue.reverse()

print(','.join(queue), end='')
        
print(']')