문제 설명
문제는 이 곳 링크를 참조하길 바란다.
시간 초과 코드
def solution(n, k, cmd):
arr = []
ori = []
dump = []
for i in range(n):
arr.append(str(i))
ori.append(str(i))
for i in cmd:
temp = i.split()
if temp[0] == 'D':
k += int(temp[1])
elif temp[0] == 'U':
k -= int(temp[1])
elif temp[0] == 'C':
dump.append([k, arr.pop(k)])
if k == len(arr):
k -= 1
else:
target = arr[k]
t = dump.pop()
arr.insert(t[0],t[1])
k = arr.index(target)
result = ''
for i in ori:
if i in arr:
result += 'O'
else:
result += 'X'
return result전체 코드
def solution(n, k, cmd):
answer = ''
linked_list = {i: [i-1, i+1] for i in range(1, n+1)}
OX = ["O" for i in range(1, n+1)]
stack = []
k += 1
for c in cmd:
if c[0] == 'D':
for _ in range(int(c[2:])):
k = linked_list[k][1]
elif c[0] == 'U':
for _ in range(int(c[2:])):
k = linked_list[k][0]
elif c[0] == 'C':
prev, next = linked_list[k]
stack.append([prev, next,k])
OX[k-1] = 'X'
if next == n+1:
k = linked_list[k][0]
else:
k = linked_list[k][1]
if prev == 0:
linked_list[next][0] = prev
elif next == n+1:
linked_list[prev][1] = next
else:
linked_list[prev][1] = next
linked_list[next][0] = prev
elif c[0] == 'Z':
prev, next, now = stack.pop()
OX[now-1] = 'O'
if prev == 0:
linked_list[next][0] = now
elif next == n+1:
linked_list[prev][1] = now
else:
linked_list[prev][1] = now
linked_list[next][0] = now
return "".join(OX)해결 방법
어렵다.... 역시 어렵다... 카카오....
옛날에 카카오 코테에서 이 문제를 못풀었던 기억이 있다. 그 때도 위의 시간초과 코드처럼 짜서 모든 테스트 케이스는 맞추었으나 효율성 평가에서 시간초과가 일어났던 것이 생각났다. 하지만 만약 리스트로 작성해야 한다면 저렇게 작성을 한 것이 맞다고 생각 하므로 시간 초과 코드도 함께 첨부 하였다. 그리고 정답인 코드는 이중 연결리스트로 작성한 것으로 다른 사람의 코드를 배낀것이다.
그 분의 해결법을 링크와 함께 적어 놓겠다.
- 이중 연결리스트를 사용하여 삽입과 삭제의 시간복잡도가 O(1)이 되도록 하는 것이 포인트다. ("cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다." 라는 언급을 보았을 때 탐색은 비교적 적게 할 것이라는 힌트를 유추할 수 있다.)
(1) 앞뒤가 연결되어 있는 1부터 n까지의 연결 리스트, 정답을 판별하기 위한 OX배열, 삭제한 것을 되돌리기 위한 stack 생성. k는 현재 선택한 요소.
(2) 'D xx', 'U xx' 일 경우, xx만큼 연결 리스트의 앞이나 뒤로 이동한다.
(3) 'C' 일 경우, 현재 선택한 연결 리스트의 정보를 가져오고, 이 정보를 stack에 넣어준 뒤 OX배열을 X로 고쳐준다. 현재 선택하고 있는 연결 리스트를 삭제한 연결리스트의 next로 이동한다(현재 보는 것이 마지막 요소라면 prev로 이동시킨다). 삭제(연결 해제)한 연결 리스트의 앞과 뒤를 연결한다(삭제한 연결리스트가 맨 앞과 맨 뒤라면 추가적인 예외처리가 필요하다).
(4) 'Z' 일 경우, stack에서 연결 리스트를 하나 가져오고, OX배열을 O으로 고쳐준다. 꺼내온 연결 리스트에서 연결리스트[꺼내온거 prev]의 다음을 현재 자기자신으로, 연결리스트[꺼내온거 next]의 이전을 자기자신으로 바꿔준다.
- 이 사이트를 그냥 거의 갖다 넣었다고 해도 무방할 정도로 참조를 했다.
