읽기 전

  • 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
  • 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 표 편집

문제 풀이

유니온 파인드로 풀 수 있지 않을까 생각했지만 삭제 순간은 현재 지점을 지우면 되지만 복구 지점은 이전 위치에 복구해야 한다는 점과 마지막으로 삭제한 노드의 양쪽 지점은 삭제되지 않은 상태라는 점을 참고해 이중 연결리스트라면 O(1)에 가능할 수도 있겠다 생각했다. C라면 포인터의 개념을, 파이썬이라면 메모리가 가리키는 변수공간에 대한 고려를 할 수 있는가 판단하는 문제였다고 생각한다. 시간 내에 문제를 해결하긴 했지만 해설을 보니 세그먼트나 팬윅트리로도 해결할 수 있다는데 일단 스킵.

  • 현재 값, 좌측, 우측 포인터를 변수로 갖는 리스트 노드 정의
  • 커서를 다루기 위해 양쪽 끝을 -1로 무효 노드로 두고 사이에 배열을 순회하면서 넣는다. 별도의 동일한 변수를 연결시켜서 한 변수는 그대로 첫번째를 가리키게 한 뒤 k번 이동해서 초기 커서의 위치를 설정한다.
  • 각 명령에 따라 행동하되 C입력 시 스택에 삭제 노드의 왼, 오른쪽을 초기화하지 않고 그대로 스택에 넣어 복구 시 찾아갈 수 있도록 한다. 그리고 커서를 조건에 맞춰서 이동시킨다.
  • Z입력 시 스택에 가장 마지막으로 삭제된 노드를 가져와 이전 노드와 이후 노드를 변수에 할당해 다시 복구시킨다.

코드가 굉장히 길어지는 문제였는데도 정답률이 꽤 높다는게 좌절스럽다.

python 코드

class ListNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def solution(n, k, cmd):
cur = head = node = ListNode(-1)
for i in range(n):
new = ListNode(i)
node.right = new
new.left = node
node = node.right
new = tail = ListNode(-1)
node.right = new
new.left = node
node = node.right
for i in range(k + 1):
cur = cur.right
stack = []
for i in range(len(cmd)):
if len(cmd[i]) == 1:
if cmd[i] == "C":
if cur.right.val == -1:
stack.append(cur)
cur.left.right, cur.right.left, cur = cur.right, cur.left, cur.left
else:
stack.append(cur)
cur.left.right, cur.right.left, cur = cur.right, cur.left, cur.right
elif cmd[i] == "Z":
reg_node = stack.pop()
prev = reg_node.left
nxt = reg_node.right
prev.right = reg_node
nxt.left = reg_node
else:
op, x = cmd[i].split()
if op == "U":
for _ in range(int(x)):
cur = cur.left
elif op == "D":
for _ in range(int(x)):
cur = cur.right
answer = ["X" for _ in range(n)]
buf = []
while head:
buf.append(head.val)
head = head.right
cnt = 0
for b in buf[1:-1]:
answer[b] = "O"
return "".join(answer)

'Algorithms > Programmers' 카테고리의 다른 글

Programmers. 프렌즈4블록  (0) 2021.09.10
Programmers. 경주로 건설  (0) 2021.09.10
Programmers. 자물쇠와 열쇠  (0) 2021.09.10
Programmers. 징검다리 건너기  (0) 2021.09.09
Programmers. 호텔 방 배정  (0) 2021.09.09

+ Recent posts