우선 이렇게 쉬운 문제를 자꾸 엉뚱한 데서 틀려서 고생을 하다니 부끄러워서 잠이 오질 않는다... ㅋㅋㅋㅋㅋㅋ
아무튼 반성하는 마음으로 기록을 해보고자 한다.
문제 링크
https://www.acmicpc.net/problem/5430
풀이 전 계획과 생각
문제를 간단히 요약하면 하나의 정수 리스트에 대응하는 함수 문자열에서 R이 나오면 정수 리스트의 순서를 뒤집고 D가 나오면 0번을 제거하며 더 이상 뺄 것이 없는데 D가 더 많이 나오면 'error'를 출력하는 것이다.
우리는 우선 이러한 절차를 문자 그대로 입력해서 제출하면 백준에서는 '시간 초과'가 뜰 것이라고 쉽게 예상할 수 있다.
그것 말고도 어려운 점이 하나 더 있는데,
정수 목록을 엔터 키나 공백으로 구분하는 것이 아니라 실제 배열처럼 [n1,n2,n3,n4,....nm] 이런 형식으로 입력을 받아야 한다는 것이다.
,를 제거하려면 문자열에 대하여 .split(',')을 하는 건 아는데... ㅠㅠ
여기저기 찾아보니 앞뒤의 대괄호를 제거하려면 첫 글자와 마지막 글자를 제거하는 [1:-1]를 쓰면 되는 것 같다.
이걸 하지 않고 입력을 다 받은 뒤에 해당 값에서 첫 글자를 지우고 마지막 글자를 지우는 연산을 일일이 다시 하는 방법을 했더니 왜인지 백준 제출창에서 ValueError가 떴다. 아마 배열이 빈 경우에 잘 처리가 안 되었기 때문이겠지?
그 다음 어려움은 당연히도 시간초과였다.
이것에 대해서는 정답률이 20%인 워낙 어려운 문제라 주최측(!)에서 직접 힌트를 주셨는데...
R이 나올 때마다 진짜로 배열을 뒤집으면 당연히 시간 초과가 뜬다는 것이다! ㅋㅋㅋ 배열이 얼마나 큰지 모르는데 그걸 일일이 매번 호출한다고 하면... ㅋㅋㅋ
그냥 R이 홀수면 뒤집히고 짝수면 안 뒤집히는 걸로 개수만 세는 게 맞다고 한다.
즉 R이 나왔을 때 실제로 안 뒤집었으니까... D가 나올 때는 어떻게 해야 한다?
현재 R이 짝수면 첫 글자를 버리고, 홀수면 마지막 글자를 버려야 한다.
풀이 (코드 블록 첨부)
# 백준 5430 AC
import sys
import collections
def r_and_d(arr):
#if len(arr[2])<arr[0].count('D'):
# return "error"
is_inorder=True
while arr[0]:
current_f=arr[0].popleft()
if current_f=='R':
is_inorder=not is_inorder
elif current_f=='D':
if len(arr[2])<1:
return "error"
else:
if is_inorder==True:
arr[2].popleft()
else:
arr[2].pop()
if is_inorder==False:
arr[2].reverse()
separator=','
str_to_return=separator.join(arr[2])
return '['+str_to_return+']'
T = int(sys.stdin.readline())
f_arr = collections.deque([[] for x in range(T)])
for x in range(T):
f_arr[x].append(collections.deque(list(sys.stdin.readline().strip())))
f_arr[x].append(int(sys.stdin.readline()))
f_arr[x].append(collections.deque(list(sys.stdin.readline().rstrip()[1:-1].split(','))))
#f_arr[x].append(collections.deque(list(sys.stdin.readline().rstrip("[ ]\n").split(','))))
#f_arr[x][-1][0]=f_arr[x][-1][0][1:]
#f_arr[x][-1][-1]=f_arr[x][-1][-1][:-1]
if f_arr[x][1]==0:
f_arr[x][2]=collections.deque([])
#print(f_arr[0])
for in_arr in f_arr:
print(r_and_d(in_arr))
풀이하면서 막혔던 점과 고민
여기까지 보면 그렇게 어려운 문제인 것 같지 않다.
그런데 왜 정답률이 20%이고 나도 계속 틀렸냐고? ㅋㅋㅋ
의외의 함정이 있었다.
우선 처음에는 'error'를 출력하면서 조기 종료되지 않는 함수에 대해서는 그냥 배열 전체를 출력하도록 했다.
그러니까 [n1, n2, n3, ...,nm] 이런 식으로 출력되도록 했던 것이다.
그런데 이 문제에 나와 있는 예제의 출력 양식을 살펴보자.
[2,1]
error
[1,2,3,5,8]
error
😱😱😱😱😱😱😱😱😱😱😱
없어!!!!!! 쉼표 뒤에 공백이 없어!!!!!!!!!!!
[1, 2, 3, 5, 8]과 [1,2,3,5,8]은 달라!!!!!!!!!!!!
🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣
이런 걸 헷갈려서 영원히 틀리다니 ㅋㅋㅋㅋㅋㅋㅋ
즉 배열을 그대로 출력하면 안 되고 공백 없이 쉼표로 연결하고 대괄호로 엮는 문자열을 만들어서 출력해야 하는 것이다.
참고로 나는 안 틀렸지만 다른 분들이 많이 틀리는 예시 하나를 더 들자면 뺄 것이 없는데 D가 뜨는 건 error를 출력하는 게 맞지만 빈 배열에 대하여 R이 뜨는 건 그냥 빈 배열 []을 그대로 출력하면 된다.
풀이 후 알게된 개념과 소감
파이썬의 문자열 입력과 처리 방법에 대해서 다시 공부하는 계기가 되었고 문제를 잘 읽어봐야 한다는 것을 깨달았다. ㅋㅋㅋ
또한 파이썬의 문자열 처리 내장 함수 중 .count('S')는 상당히 처리 시간이 오래 걸려서 안 쓰는 것만도 못할 수 있다는 것을 알게 되었다.
마지막에 D가 너무 많으면 그냥 처리하지 않고 error를 출력하며 조기 종료하는 조건문을 삽입해 보았는데 처리 시간이 오히려 늘어난 것을 확인할 수 있다.
