문제 해석
- 배열이 주어지는데 R→ 뒤집기, D→ 처음 수를 빼기이다.
- 함수를 적용한 이후의 배열을 출력하시오
문제 풀이 idea ( 1차)
- 문제를 주어진 조건대로 풀고자 R이 나오면 뒤집고 (reverse)
- D가 나오면 처음 수를 빼고자 하였다. (deque의 popleft)
1차코드
from collections import deque
T=int(input())
for i in range(T):
func=input()
number=int(input())
array=deque(eval(input()))
for i in func:
if i=="R":
array.reverse()
if i=="D":
if array!=deque([]):
array.popleft()
else:
array="error"
break
if array=="error":
print(array)
else:
answer="["
for i in array:
answer+=str(i)
answer+=','
answer=answer[:-1]
answer+="]"
print(answer)결과는… 시간초과
질문게시판을 보니 reverse를 쓸 경우 배열이 길어지게 될때 시간이 오래걸린다고 한다.
💡 1. R 명령이 들어온다고 진짜로 배열의 모든 원소를 뒤집으면 절대로 안 됩니다. N개의 원소의 순서를 정말로 바꾸면 당연히 그 원소 수만큼 시간이 걸리고, 그걸 최대 10만 번 수행해야 하니 테스트 케이스 1개만으로도 100억번의 연산이 수행됩니다. R 명령의 핵심은 실제로 원소를 뒤집지 않고도 뒤집힌 것과 같은 효과를 내도록 구현하는 것입니다. C++의 std::reverse(), Python의 a[::-1] 역시 사용해서는 안 됩니다.
💡 2. D 명령에 대해서 보통 배열의 맨 앞 원소를 무작정 지워서는 안 됩니다. C++의 vector::erase(), Java의 ArrayList.remove(), Python의 list.pop() 등으로 배열의 첫 번째 원소를 지울 시, 그 뒤에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨오게 되므로, 그 시간 역시 원소의 수에 비례하여 소요됩니다. 라이브러리 함수는 호출만 하면 N개의 원소를 기적같이 O(1)에 처리해주는 마법사가 아닙니다. 저렇게 원소를 당겨오는 작업 없이도 D의 기능을 구현할 수 있어야 합니다.
💡 3. 빈 배열은 []로 출력해야 합니다. 아무것도 출력하지 않거나, error를 출력하거나, 무조건 원소를 하나 출력하고 시작하려고 하면 안 됩니다.
💡 4. 배열이 비어있는데 R을 하는 건 에러가 아닙니다. D만 에러입니다. 처음에 수가 0개여도 D가 없다면 error가 아닐 수 있습니다.
💡 5. 테스트 케이스마다 초기화가 잘 됐는지 확인하세요. 그리고 매 케이스마다 개행 문자를 항상 출력하는지 확인하세요.
💡 6. 처음 배열의 상태에 대한 문자열의 길이는 최대 400001자입니다. 입력 문자 배열 크기를 잘 설정하세요.
💡 처음 배열의 상태로 빈 배열이 주어지는 경우를 조심하세요. 수가 무조건 하나 이상 있다고 가정하고 코드를 작성하면 이런 경우를 제대로 처리하지 못할 수 있습니다.
💡 7. 조건문 안에 strlen(str) 를 절대로 넣지 마세요. strlen은 문자열의 처음부터 널 문자가 나올 때까지 한 글자씩 확인하므로, 반복문을 한 바퀴 돌 때마다 문자열의 길이만큼의 시간이 걸립니다.
💡 8. R과 D의 개수만 세고 나중에 몰아서 처리하면 안 됩니다. R을 할 때마다 D를 했을 때 지워지는 원소가 달라지기 때문입니다. [1,2,3] 배열에서 DRD 명령을 수행하면 어떻게 되어야 할지 생각해 보세요.
💡 9. 배열에 들어있는 수는 최대 100입니다. 무조건 한 글자로 가정하고 구현하면 안 됩니다. 참고로, 예제에도 두자리의 수가 하나 등장하지만 어차피 지워지는 원소이기 때문에 잘 나오는 것처럼 보일 수도 있으므로 실제로 두 자릿수를 정확하게 출력하는지 직접 예시를 만들어 출력해보아야 합니다. 대표적인 실수로, 답을 통째로 문자열로 저장해놓고 R 명령시 그대로 뒤집는 것이 있습니다. 이렇게 하면 각 수의 자릿수까지 잘못 뒤집어지게 되는 불상사가 발생합니다.
💡 10. 입출력 양식은 공백의 유무까지 정확하게 고려해야 합니다. 예제 입출력을 확인해 보세요. 배열의 수들 사이에는 공백이 없으며, 입력받을 때 공백이 있어야만 입력받을 수 있는 방밥을 쓰거나 출력할 때 임의로 공백을 삽입해서 출력하면 안 됩니다. 대표적인 예시로, Python에서 print(list)를 하면 원소들 사이에 불필요한 공백이 출력되어 틀립니다.
해당 1번과 10번의 조언을 듣고 코드를 고쳤다.
새로운 문제풀이 idea
- Reverse를 안하기 위해선 어떻게 해야할까?
- 실제로 뒤집지 말고 뒤집힌경우 뒤집혔다고 가정하고 pop으로 마지막 항목을 빼자
- 그 다음 마지막에 리스트 마지막부터 출력해주면 되지않을까???
- 뒤집혔다의 가정??? → status라는 boolean 변수를 통해 True면 정방향으로, False면 역방향이라고 가정하자!
- 역방향= 뒤집혔다. 정방향 = 처음상태방향이다.
from collections import deque
T=int(input()) # 테스트 케이스 수
for i in range(T):
func=input() # 함수 (RDD)입력
number=int(input()) # 배열 개수 입력
array=deque(eval(input())) # deque를 입력받음. 문자열처럼 받는 list를 list로 바꾸기 위해 eval 함수 사용.
status=True # True=정방향, false=역방향을 표시하기 위함 ( reverse 대체 )
for i in func: # 함수 실행
if i=="R": # R일경우
status=not status # 방향을 바꿔준다.
elif i=="D":
if status==True: # 정방향일경우
if array!=deque([]): # 빈 리스트가 아니라면
array.popleft() # 앞에서 뺀다.
else:
array="error" # 예외처리
break
else:
if array!=deque([]): # 빈리스트가 아니라면
array.pop() # reverse로 뒤집었다 치면 맨 뒤가 맨 앞이기 때문에 맨 뒤를 pop한다.
else:
array="error"
break
if array=="error": # 예외처리
print(array)
else:
if array==deque([]): # 빈 리스트면 빈 리스트를 출력
print("[]")
else:
result=['['] # 추후 추가해주기 위해 [ 만들기
answer=[] # 정답 넣을 곳
if status==True: # 정방향일 경우
for i in array:
answer.append(str(i))# 순서대로 꺼내서 넣음
else: # 역방향일경우
for i in range(len(array)-1,-1,-1): #
answer.append(str(array[i]))#순서대로 꺼내서 넣음
answer=','.join(answer) # ,로 join시켜줌
result.append(answer)# [ answer되게 만듬
result.append(']')# ] 추가
print(''.join(result)) #공백없이 join해서 print해줌
answer='[' # 추후 추가해주기 위해 [ 만들기
if status==True: # 정방향일 경우
for i in array:
answer+=(str(i))# 순서대로 꺼내서 넣음
answer+=','
else: # 역방향일경우
for i in range(len(array)-1,-1,-1): #
answer+=(str(array[i]))#순서대로 꺼내서 넣음
answer+=','
answer=answer[:-1]
answer+="]"
print(answer)- 마지막 부분을 그냥 문자열을 추가해가는걸로 만들었는데 오히려 더 오래걸린다….
-> 정답 코드 메모리, 시간
-> 밑의 문자열로 바로 받아서 출력한 결과
import sys
input=sys.stdin.readline() # 오히려 시간과 메모리가 더 많이 들었다.
별론데..