[백준/Python] 5430 AC
문제만 봤을 때는 너무 간단해보여서 골드 문제도 척척 풀어내는 나, 어쩌면 성장했을지도?! 라고 생각하면서 아이패드에 어떤식으로 풀지 정리도 안하고 바로 코드를 술술 적어내려갔는데......
그럼 그렇지, 시간초과^^
1. 시간 초과 코드 & 설명
T = int(input())
for _ in range(T):
operations = []
x = []
for i in (input()):
operations.append(i)
n = int(input())
for i in (input()):
if i.isdigit():
x.append(int(i))
for p in operations:
if p == 'R':
x = x[::-1]
elif p == 'D':
if len(x) == 0:
break
else:
x = x[1:]
if len(x) == 0:
print('error')
else:
print(x)보다시피 주석도 한 줄 없고 그냥 문제에서 보이는 그대로 코드를 작성했다.
심지어 나중에 생각해보니까 코드도 틀렸음...ㅋ 예제에서
DD
1
[42]
이 부분에서 x가 ['4', '2'] 이렇게 되니까... 이 예제에서는 맞는 답이 나오지만 코드로나 시간초과로나 어쨋든 틀렸음....
나는 '시간초과'가 뜨면 뇌정지가 오는데, 시간 복잡도 공부를 제대로 해놓지 않은 탓에
어디에서 어떻게 시간을 줄여야할지, 좀 더 대공사를 해야한다면 어떻게 기존 방식을 버리고 새로운 방식으로 풀어봐야할지 전.혀. 생각을 할 수 없다는 것임......ㅜ 자랑은 아니고 훈련이 더 필요할 거 같음...
그래서 생각해낸 방법이 deque 이용하기.
계속 뒤집고 숫자 빼고, 숫자 빼고 뒤집고, 뒤집고 뒤집고 숫자빼고 뭐 이런 거 하는 거니까 앞/뒤에서 문자 추가/삭제에 용이한 deque를 이용하면 어떨까 하는 생각으로 deque의 시간복잡도를 검색해봤다!
list의 append/pop 시간복잡도는 O(n)인데, (고정된 사이즈를 갖는 array 형태라서)
deque의 append/pop 시간복잡도는 O(1) 이었다!!!!!!!
그래서 deque를 무.족.권. 이용해야겠다 싶어서 좀 더 생각을 해봤는데,
deque가 양방향 자료형이라 pop도 있고 popleft도 있잖음?
이 말이 무엇이냐,
★reverse 한 번 하고 delete를 하는 거는 그냥 reverse를 안하고 맨 오른쪽에서 pop을 하는거고,
★reverse 두 번 하고 delete를 하는 거는 reverse를 안하고 맨 왼쪽에서 popleft를 하는 거랑 똑같다는 말임
나는 reverse의 개수가 홀수 개일 때만 마지막에 reverse해서 출력만 해주면 되는거임~
2. 통과된 코드 & 풀이과정
from collections import deque
T = int(input())
for _ in range(T):
operations = deque()
for i in (input()):
operations.append(i)
n = int(input())
x = deque(input()[1:-1].split(','))
if n == 0:
x = deque([])
# print('len(x) =', len(x))
# 마지막에 flag = 1이면 R의 개수가 홀수 개라고 판단하고 reverse 해서 출력하고,
# flag = 0이면 reverse 안하고 출력
flag = 0
emptyFlag = 0
while operations:
op = operations.popleft()
if op == 'R' and flag == 0: # R 개수 짝수 개였는데 flag = 1 하면서 홀수 개라고 상태 update
flag = 1
elif op == 'R' and flag == 1: # R 개수 홀수 개였는데 flag = 0 하면서 짝수 개라고 상태 update
flag = 0
elif op == 'D':
if len(x) == 0:
emptyFlag = 1 # print('error') 함
break
elif x and flag == 0: # R 개수가 짝수 개이므로 delete는 왼쪽 끝에서
x.popleft()
elif x and flag == 1: # R 개수가 홀수 개이므로 delete는 오른쪽 끝에서
x.pop()
if emptyFlag == 1:
print('error')
else:
if flag == 1:
# x = x[::-1] => deque는 [::-1]로 슬라이싱이 안됨 -> .reverse() 사용
x.reverse()
print('[', end='')
print(','.join(x), end='')
print(']')풀이과정
1. T, operations, n, x를 입력받는데, operations는 R 또는 D를 각각 리스트 형태로 받고, x는 숫자만 deque형태로 받음
2. flag를 이용해 R의 개수가 홀수인지 짝수인지 계산 → 마지막의 flag가 1이면 reverse 해줌
2-1. flag = 1은 R의 개수가 홀수 개인 상태
2-2. flag = 0은 R의 개수가 짝수 개인 상태
3. operations에 있는 수행할 함수를 하나씩 빼서 flag에 상태를 update
3-1. 함수가 R 이면, 현재 상태를 flag에 update한다
(R의 개수가 짝수였는데, 또 R이 나왔다면 flag를 1로 바꾸어 현재 R의 개수가 홀수임을 update)
(R의 개수가 홀수였는데, 또 R이 나왔다면 flag를 0로 바꾸어 현재 R의 개수가 짝수임을 update)
3-2. 함수가 D 일 때
현재 flag = 1(R의 개수가 홀수)이면, 오른쪽 끝에서 요소를 빼는 pop()
현재 flag = 0(R의 개수가 짝수)이면, 왼쪽 끝에서 요소를 빼는 popleft()
현재 x에 아무것도 없으면, emptyFlag를 1로 바꾼 후 break해 while문을 빠져나감 (error 출력해야함)
4-1. emptyFlag = 0이면, error를 출력
4-2. flag = 1이면, x를 reverse해 출력
5. 현재 x는 deque이므로 .join()을 이용해 모든 요소들을 '예제출력'의 형태로 출력해줌
에러 설명
마지막에 reverse를 하는데 처음에 시간초과났던 코드에서 썼던 [::-1]를 쓰니까 에러가 남....... 마지막까지;;
찾아보니까 deque는 저런 슬라이싱 방법을 사용할 수 없다고 합니다....~
그래서 그냥 .reverse() 씀^~^
reverse()도 시간복잡도가 O(n)이라, 만약에 R이 나올 때마다 .reverse() 했으면 또 시간초과될 뻔;;;
얻어걸린 거지만 그래도 마지막에 R 개수가 홀수 개일때만 reverse하길 아주 잘한듯!!!~