https://programmers.co.kr/learn/courses/30/lessons/81303
초반에 제출한 코드는 다음과 같다. 존재하지 않으면 boolean값을 False로 두어 건너뛰도록 했다.
이때, 정확성 테스트는 모두 통과했으나 효율성 테스트는 절반만 통과했다.
def solution(n, k, cmd):
bool_table = [True for _ in range(n)]
selected_idx = k
exist_max_idx = n-1
deleted_idx_list = []
for one_cmd in cmd:
splited_cmd = one_cmd.split()
if splited_cmd[0]=="Z":
deleted_idx = deleted_idx_list.pop()
bool_table[deleted_idx] = True
exist_max_idx = max(exist_max_idx,deleted_idx)
elif splited_cmd[0]=="C":
deleted_idx_list.append(selected_idx)
bool_table[selected_idx] = False
if selected_idx == exist_max_idx:
while not bool_table[selected_idx]: # 다음이 False일 수 있다!
selected_idx -= 1
exist_max_idx = selected_idx
else:
while not bool_table[selected_idx]: # 다음이 False일 수 있다!
selected_idx += 1
elif splited_cmd[0]=="U":
distance = int(splited_cmd[1])
while distance != 0:
selected_idx -= 1
if bool_table[selected_idx]:
distance -= 1
elif splited_cmd[0]=="D":
distance = int(splited_cmd[1])
while distance != 0:
selected_idx += 1
if bool_table[selected_idx]:
distance -= 1
return "".join(["O" if x else "X" for x in bool_table])
위 코드는 Z의 경우 O(1)이지만 C,U,D의 경우 O(N)이다. 따라서 양방향 연결리스트를 통해 시간복잡도를 낮춰야 한다.
아래 코드에서 C, Z는 O(1), U,D는 O(X)로 만들었다. X: 남아있는 행수
(출처)
def solution(n, k, cmd):
cur = k # 현재 index
answer = ['O'] * n # 정답인 존재하는지 여부
table = { i:[i - 1, i + 1] for i in range(n) }
table[0] = [None, 1]
table[n - 1] = [n - 2, None]
stack = [] #삭제한 행 정보 넣어두는 stack (prev,cur,next)형태로
for c in cmd:
if c == "C":
# 삭제
answer[cur] = 'X'
prev, next = table[cur]
stack.append([prev, cur, next])
if next == None:
cur = table[cur][0]
else:
cur = table[cur][1]
if prev == None:
table[next][0] = None
elif next == None:
table[prev][1] = None
else:
table[prev][1] = next
table[next][0] = prev
elif c == "Z":
# 복구
answer[now] = 'O'
prev, now, next = stack.pop()
if prev == None:
table[next][0] = now
elif next == None:
table[prev][1] = now
else:
table[next][0] = now
table[prev][1] = now
else:
# 커서 이동
c1, c2 = c.split(' ')
c2 = int(c2)
if c1 == 'D':
for _ in range(c2):
cur = table[cur][1]
else:
for _ in range(c2):
cur = table[cur][0]
return ''.join(answer)