[알고리즘] - AC (BOJ 5430)
- 이번 문제는 BOJ 5430, AC 문제입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!
입력에 대해서
-
기존에 풀던 문제와 다르게, 입력 예시를 보면 ‘[1, 2, 3, 4]’와 같이 리스트가 문자열의 형태로 들어옵니다. 그렇기에 이 입력 값을 받기 위한 처리가 필요합니다.
-
각 원소들이 ‘,’로 구분되어 있다는 점을 활용하여, 정규표현식을 이용하여 각 숫자들을 분리했습니다.
import re list_str = input().rstrip() # 스트링 형태의 문자열 '[1,2,3,4]' lst = re.findall(r'\d+', list_str) # 숫자(d)인 문자들이 연속되어 나열되는 경우들을 리스트 형태로 반환합니다. lst = [int(x) for x in lst] # 문자 형태로 되어 있는 각 숫자 원소들을 정수로 변경합니다.- 이와 같이 정규표현식을 사용하면, [1,2,3,4]와 같이 한 자리로 된 숫자는 물론이고, [4212,12345]와 같이 한 자리를 넘어가는 숫자열들도 분리하여 리스트 형태로 반환 받을 수 있습니다.
접근 방식
- 각 테스트케이스마다 명령어들은 앞에서 부터 꺼내져오기 때문에 큐 자료구조로 접근했고, 명령의 처리 대상이 되는 숫자 리스트는 순서를 바꿀 경우 인덱싱을 활용하기 위해 그대로 리스트 (스택) 자료구조를 활용했습니다.
트러블 슈팅
-
위와 같은 형태로 자료구조를 사용하면, ‘D’ 명령어를 수행할 경우 리스트의 가장 첫 번째 원소를 제거하기 위해
del(0)명령어를 사용해야 합니다. -
그러나, 스택 자료구조로 구성되어 있는 리스트는 인덱스를 통해 삭제를 시도하는 경우
log(N)의 시간 복잡도를 갖게됩니다. -
또한, ‘R’ 명령어 실행 시에 수행되는 리스트 원소의 순서를 뒤집는 행위도 log(N)의 시간 복잡도를 갖게됩니다.
-
이렇게 되면, 최대 100,000의 수를 가질 수 있는 명령어들을 반복 순회하며, 역시 최대 100,000의 수를 가질 수 있는 숫자 리스트들에 대해 log(N)의 작업을 수행할 경우, 테스트케이스 한 번만으로도 이미 주어진 시간 복잡도를 초과하게 됩니다.
해결 방안
-
위의 문제를 해결하기 위해선, 우선 첫 번째 원소를 삭제하는 과정에서 log(1)의 복잡도로도 처리할 수 있도록 숫자 리스트를 큐 자료구조로 변경해야 합니다.
-
다음으로 ‘R’ 명령어 실행 시에 수행되는 리스트 내부의 순서를 뒤집는 행위를 없애기 위해선, 아이디어가 필요합니다. 생각해보면, ‘R’ 명령어를 실행할 때 굳이 숫자 리스트의 내부를 실제로 뒤집을 필요가 없습니다. 명령어가 ‘R’과 ‘D’로 제한되어 있는 상황이기 때문에, ‘R’ 명령어를 실행하여 실제로 숫자 리스트의 내부 순서를 뒤집는 것이 ‘D’ 명령어를 실행할 때 꼭 필요한 일인지 생각해봐야 합니다.
-
‘D’ 명령어로 실행되는 것은 가장 앞에 나오는 원소를 삭제하는 행위입니다. 그렇기에 ‘R’ 명령어를 실행했을 때, 실제 숫자 리스트의 순서를 뒤집지 말고, ‘D’ 명령어를 만났을 때 가장 뒷 쪽의 나오는 원소를 삭제하도록만 해주면 됩니다.
-
이를 위해 flag 변수를 사용하여 삭제시의 방향을 설정하고, ‘R’ 명령어를 만나면 해당 변수만을 뒤집어 주면 됩니다.
-
-
이때 주의해야 할 점은, flag 변수가 뒷 쪽 방향을 가리키고 있는 상태에서 모든 명령어를 실행한 뒤 결과 리스트를 출력할 경우, flag 변수를 확인하여 해당 리스트를 뒤집어 주는 작업이 마지막에 필요하다는 점입니다.
구현
- 위의 아이디어를 바탕으로 구현한 코드는 아래와 같습니다.
# BOJ 5430, AC
import sys, re
from collections import deque
input = sys.stdin.readline
test_num = int(input().rstrip())
result = []
for _ in range(test_num):
stmt = deque(list(input().rstrip()))
lst_size = int(input().rstrip())
lst_str = input().rstrip()
# '[1,2,3,4]'로 구성된 문자열에서 숫자만을 파싱
lst = re.findall(r'\d+', lst_str)
lst = deque([int(x) for x in lst])
# 가장 앞 원소를 제거하는 방향으로 초기화
que_dir = True
while stmt:
tg = stmt.popleft()
# Reverse일 때
if tg == "R":
# 삭제하는 방향 변경
que_dir = not que_dir
# Delete일 때
else:
# 비어있을 때 해당 문자열이 수행되면 error
if not lst:
lst = 'error'
break
else:
if que_dir:
# 가장 앞 문자 제거
lst.popleft()
else:
# 가장 뒷 문자 제거
lst.pop()
# deque를 list로 변경하여 저장
if lst != 'error':
# 반대 방향으로 되어있다면, 리스트를 반대 방향으로 바꿔줌
if not que_dir:
answer = list(lst)[::-1]
else:
answer = list(lst)
result.append(answer)
else:
result.append(lst)
# 결과를 모두 확인한 뒤 출력
for elem in result:
print(elem)
그러나,,,
-
위의 소스코드는 오답을 뿜어냅니다.. 어떤 반례가 있을지 한참을 고민하던 중, 예시 출력이 리스트 형태가 아니라는 것을 확인했습니다. 즉, print(lst)를 통해 출력 되는 리스트는
[1, 2, 3, 4, ...]와 같이 원소 사이를 공백으로 구분하지만, 문제에서 원하는 출력에는[1,2,3,4,5...]와 같이 원소들 사이에 공백이 없는 형태를 원하는 것입니다. -
이를 인지하고, 리스트를 출력 형태에 맞춰서 문자열로 변경한 뒤 제출하니 정답을 얻을 수 있었습니다. 해당 코드는 아래와 같습니다.
# 최종 리스트를 출력 형식에 맞게 공백 없는 리스트 문자열로 변환 answer_str = "[" for i, elem in enumerate(answer): if i != 0: answer_str += ',' answer_str += str(elem) answer_str += "]" result.append(answer_str)
Lesson
알고리즘 문제를 풀다보면, 사소한 착각이나 실수로 놓친 부분에서 걷잡을 수 없는 오류가 발생하기도 합니다. 당연하다고만 생각하는 부분에 대해서 철저하게 고민하고, 정확한 답을 출력할 수 있도록 주의를 기울여야 할 것 같습니다.