처음 푸는 골드 문제였다,,
언뜻 보기에 골드치고는 굉장히 쉬운 것 같았는데
함정들이 많아서 못 풀었다.
그래도 새로 알아 가는 건 많은 것 같다!
해결 포인트 1 : 인덱싱
보통 문제에서 리스트, 덱 같은 문제면 출력 시 [1, 2, 3] 이렇게 출력시키지 않고
1 2 3 이렇게 출력되게 하는 문제들이 많았는데 이 문제는 대괄호와 쉼표를 포함해서 난감했다.
또, 입력 시에도 대괄호와 쉼표를 포함해서 난감했다,,
1. 입력
입력 시 쉼표는 split(",")을 통해서 처리할 수 있었다.
하지만, 양끝의 대괄호를 저장할 때 어떻게 없앨 지 감이 안 잡혀서 정답을 봤다.
허무했다,, 대괄호의 위치가 바뀌는 것이 아니기 때문에 양 끝을 제외해서 슬라이싱하면 되는 것이었다.
[1:-1]로 슬라이싱하면 해결된다!
2. 출력
출력 시에는 대괄호는 print문 양 끝에 추가하면 되므로 쉬웠지만,
쉼표를 출력하는 게 어려웠다.
여기서 join함수를 새로 알았다!
A = [1, 2, 3, 4]
print(",".join(A)) 👉 A의 요소들이 "," 즉, 쉼표를 기준으로 하나씩 구분되어 결합된다!
👉 1, 2, 3, 4 출력
해결 포인트 2 : 시간 복잡도 고려
테스트 케이스를 해서 다 통과해서 제출을 해봤는데 시간 초과였다.
실버 문제부터는 시간 복잡도를 고려해야 풀리는 문제들이 많았다.
이 문제도 시간 복잡도를 고려해야하는 함정이 있었다.
바로, 함수 R에 시간을 쓰지 않아도 되는 경우가 있었다.
함수 R을 쓸 때는 배열을 뒤집는 것인데 이때 시간복잡도가 배열의 크기만큼 뒤집으므로
한 번 시행마다 O(N)이다.
하지만 R이 연속으로 2번, 좀 더 자세히 말하면 R이 연속으로 짝수번 나오면 원래의 배열과 다름이 없기 때문에 R을 시행하지 않아도 된다.
이러한 함정도 결국 구글링을 해서 찾아냈지만 구현하는 방법은 내가 해보기로 했다.
내 풀이
if AC.count("RR") > 0:
AC.replace("RR","")AC는 함수가 주어지는 공간이다.
나는 처음에 단순히 RR을 지우면 필요없는 R이 없어져서 배열을 뒤집지 않아도 되니까
시간복잡도가 줄어들 줄 알았는데 여전히 시간초과가 떴다.
이유를 생각해보니, 결국 replace를 하려고 "RR"을 찾기 위해 배열 전체를 돌면서 바꾸니까 시간복잡도는 O(N)에서 변한 것이 없는 것 같았다!!
정답
for k in range(len(AC)):
if AC[k] == "R":
cnt += 1
elif AC[k] == "D":
if cnt % 2 == 0:
if len(num_deque) == 0:
error_cnt += 1
break
else:
num_deque.popleft()
else:
if len(num_deque) == 0:
error_cnt += 1
break
else:
num_deque.pop()
# 여기서도 reverse해서 popleft를 하지 않고 reverse해서 popleft는 결국 pop과 같으므로 pop을 쓴다.
if error_cnt != 0:
print("error")
continue
if cnt % 2 == 0:
print("[" + ",".join(num_deque) +"]")
else:
num_deque.reverse()
print("[" + ",".join(num_deque) +"]")👉 AC[k] == "R"일때마다 R 함수를 실행하는 것이 아니라(뒤집는 것이 아니라)
cnt를 더하면서 R이 몇 번 나왔는지를 count한다.
AC[k] == "D"일 때는 R이 몇 번인지에 따라 D 함수의 동작이 바뀌므로 cnt로 체크한다.
cnt가 짝수라면, 배열이 안 바뀐 것이므로 똑같이 첫 번째 수를 버리고,
cnt가 홀수라면, 배열이 뒤집힌 것이므로 원래 첫 번째 수인 뒤집힌 배열의 마지막 수를 버린다.
마지막으로, 출력 시 cnt가 짝수라면, 그대로 위에서 R, D 함수로 동작된 배열을 출력하고
cnt가 홀수라면, reverse를 해야하는데 reverse가 되지 않았기 때문에 reverse를 한 후 출력한다.
💡 for문 안에서 AC[k] == "R" 일때마다 배열을 뒤집는 것이 아니라 for문 안에서는 단순히 count를 한 후 출력 시에 뒤집어서 출력하는 생각!
