처음에 잘 못풀어서 카카오 풀이를 보고 풀었던 문제로 효율성 테스트까지 통과하려면 연결 리스트를 사용해서 풀어야하는 문제입니다.
그런데 연결리스트로 구현하는걸 알더라도 각 노드의 prev와 next가 None일 때 에러가 나는걸 처음에 고려하지 않은채 풀어서 푸는데 꽤 시간이 걸렸습니다.
|
1
2
3
|
// 아래와 같은 코드를 작성할 때
// node.prev가 None이라면 에러가 납니다.
node.prev.next = None
|
cs |
Python 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
class Node:
def __init__(self, num):
self.num = num
self.prev = None
self.next = None
def make_table(n):
prev_node = None
root_node = None
for i in range(n):
if i == 0:
node = Node(i)
root_node = node
prev_node = node
else:
node = Node(i)
prev_node.next = node
node.prev = prev_node
prev_node = node
return root_node
def make_map(n):
answer_map = dict()
for i in range(n):
answer_map[i] = 'O'
return answer_map
def get_start(k, root_node):
for i in range(k):
root_node = root_node.next
return root_node
def move_up(n, node):
for i in range(n):
node = node.prev
return node
def move_down(n, node):
for i in range(n):
node = node.next
return node
def delete(node):
if node.next is None: # 현재 행이 마지막 행인 경우
node = node.prev
if node is not None and node.next is not None:
node.next = None
else:
if node.prev is not None:
node.prev.next = node.next # 이전 행의 next 바꾸기
node.next.prev = node.prev # 다음 행의 prev 바꾸기
node = node.next
return node
def restore(del_node):
prev_node = del_node.prev
next_node = del_node.next
if prev_node is not None:
prev_node.next = del_node
if next_node is not None:
next_node.prev = del_node
def solution(n, k, cmds):
root_node = make_table(n)
node = get_start(k, root_node)
answer_map = make_map(n)
deleted = []
for cmd in cmds:
if cmd[0] == 'U':
step = int(cmd[2:])
node = move_up(step, node)
elif cmd[0] == 'D':
step = int(cmd[2:])
node = move_down(step, node)
elif cmd[0] == 'C':
deleted.append(node)
answer_map[node.num] = 'X'
node = delete(node)
elif cmd[0] == 'Z':
del_node = deleted.pop()
answer_map[del_node.num] = 'O'
restore(del_node)
answer = ''.join(answer_map.values())
return answer
|
cs |
'알고리즘' 카테고리의 다른 글
| 백준 14467번 Rust 풀이 (0) | 2021.10.10 |
|---|---|
| 백준 1913번 달팽이 Rust 풀이 (0) | 2021.10.10 |
| 백준 사회망 서비스(Python/Go) (0) | 2021.04.15 |
| 백준 단지번호 붙이기(Go) (0) | 2021.04.11 |
| 백준 아기상어 (Go) (0) | 2021.04.07 |