바킹독 연결 리스트 강의를 공부하고 풀어본 문제
파이썬에서 지원하는 자료구조에 대한 공부를 아직 하지 않았기 때문에 단순하게 배열을 활용해서 풀었다.
이중 연결 리스트에 포함되는 데이터, 이전 노드, 다음 노드를 각각의 배열로 만들었다.
0번째는 헤드 노드이며, 더미 노드이기 때문에 데이터를 갖지 않는다.
👉 리스트의 길이가 0인 경우를 판단하기 용이하기 때문에 보통 리스트는 헤드 노드인 더미 노드를 갖는다고 한다.
❗️ 자료를 삭제하는 연산이 실제로 메모리를 삭제하는 것이 아니고 배열 상에 그대로 남아 있게 되기 때문에 실무에서는 절대 좋은 코드가 아님!!
🦾 배운 점
- 자꾸 시간 초과가 나는데 아무리 봐도 시간복잡도가 높은 연산이 없고...
혹시나 해서 입력을sys.stdin.readline으로 받아보니까 해결이 됐다.
파이썬 입출력 연산이 정말 느리긴 한가 보다. - 여기서도 처음에 받은 문자열에서 개행 문자가 삭제되지 않아 문제가 생겼었는데
strip()으로 제거해주니까 바로 해결됐다.
import sys
input = sys.stdin.readline
a = [] # 문자열을 저장할 배열
next = [] # 다음 노드의 주소를 저장할 배열
prev = [] # 이전 노드의 주소를 저장할 배열
for i in range(700000) :
a.append(' ')
# 주소 배열을 -1로 초기화
next.append(-1)
prev.append(-1)
cur = 0 # 커서 시작 주소 (헤드 노드)
unused = 1 # 다음 노드를 저장할 주소
# 초기 문자열 입력받고 저장하기
tmp = input().strip()
for i in range(1, len(tmp) + 1) :
a[unused] = tmp[i - 1] # 0번째는 더미 노드이기 때문에 데이터 배열은 1번째 인덱스부터 채운다.
next[cur] = i # 다음 노드 주소 배열은 0번째 더미 노드부터 채운다.
prev[unused] = cur # 이전 노드 주소 배열은 1번째 인덱스부터 채운다.
cur = unused
unused += 1
# 명령어 입력받고 처리하기
n = int(input()) # 명령어의 개수 입력받기
for i in range(n) :
c = input() # 명령어 입력받기
if c[0] == 'L' and prev[cur] != -1 : # 현재 커서가 가리키는 노드 이전 노드가 있으면 커서를 왼쪽으로 이동
cur = prev[cur]
elif c[0] == 'D' and next[cur] != -1 : # 현재 커서가 가리키는 노드 다음 노드가 있으면 커서를 오른쪽으로 이동
cur = next[cur]
elif c[0] == 'B' and cur > 0 : # 커서가 0보다 큰 경우(데이터가 하나라도 있는 경우)에만 삭제
next[prev[cur]] = next[cur] # 이전 노드의 다음 노드를 현재 노드의 다음 노드로 연결
prev[next[cur]] = prev[cur] # 다음 노드의 이전 노드를 현재 노드의 이전 노드로 연결
cur = prev[cur] # 삭제 후에 커서가 한 칸 왼쪽으로 이동한다고 했으므로 이전 노드로 지정
elif c[0] == 'P' : # 새 문자 삽입
a[unused] = c[2] # 새 노드 생성 (unused번째에 데이터 저장)
prev[unused] = cur # 새 노드의 이전 노드는 현재 커서가 가리키는 노드
if next[cur] != -1 : # 현재 커서가 가리키는 노드의 다음 노드가 있다면
next[unused] = next[cur] # 새 노드의 다음 노드는 현재 노드의 다음 노드
prev[next[cur]] = unused # 다음 노드의 이전 노드는 새 노드
next[cur] = unused # 현재 커서가 가리키는 노드의 다음 노드는 새 노드
cur = unused
unused += 1
# 결과 출력하기
addr = next[0] # 헤드 노드가 가리키는 첫 번째 노드의 주소
while addr != -1 : # 주소가 -1이 아닌 동안 반복
print(a[addr], end = '') # 한 글자씩 출력
addr = next[addr] # 다음 노드의 주소 할당
