미소를뿌리는감자의 코딩
[백준 2024/02/10] 5397번 키로거 본문
https://www.acmicpc.net/problem/5397
1. 접근 방법
처음에 접근했던 방법은 index를 이용한 list였다.
아래 코드를 이용했고, 보기 좋게 '시간 초과' 를 당했다.. ㅜ
for i in range(int(input())):
i = 0
result = []
for letter in input():
if letter == '<':
i -= 1
if i < 0:
i = 0
elif letter == '>':
i += 1
if len(result) < i:
i = len(result)
elif letter == '-':
if i > 0:
del result[i-1]
i -= 1
else:
result.insert(i, letter)
i += 1
print(''.join(result))
그래서 어떻게 접근할까 하다가 -> double linked list로 접근해야겠다고 생각했다.
그 이유로는 list의 경우 한 값이 pop 되거나 insert할 경우 O(n) 의 시간 복잡도를 가지기 때문에 시간이 많이 소요되기 때문이다.
하지만, linked list의 경우 pop 과 insert에서 head부터 찾아서 pop이나 insert를 하지 않아도 될 경우, O(1)의 시간 복잡도를 지니기 때문이다.
여기서 함수로 구현한 부분은
__init__ : 설정 초기화
left : '<' 왼쪽 화살표일 경우
right : '>' 오른쪽 화살표일 경우
character : 문자가 입력되었을 경우
delete : '-' 가 입력되었을 경우
print : 마지막에 print하는 것
가 있다.
1) __init__
해당 경우에는 새로운 node를 만들고 그 값을 '~'으로 저장해주었다.
왜냐하면, |abc와 같이 a 앞에 커서가 위치할 수 있기 때문이다. 그 경우엔, None을 가리킬 수 있기 때문에 '~'의 값을 넣어준 node를 처음에 만들어주었다.
None을 가리킬 경우 None.next 나 None.prev에서 error가 난다.
self.current는 현재 커서가 있는 위치를 나타내기 위해서 사용하였다.
2) left
왼쪽 화살표의 경우, current.data가 '~'인 경우엔, 맨 앞에 있는 것이기 때문에 return해주도록 하였다.
3) right
self.current.next가 None인 경우엔 맨 끝에 있는 것이기 때문에 return 해주도록 하였다.
4) character
character에서 많은 시행착오를 겪었다.
3가지 경우로 나누어서 character를 삽입할 수 있었다.
[1] 처음 값이 들어올 때,
[2] 맨 뒤에 문자를 넣는 경우
[3] 문자와 문자 사이에 값을 것는 경우
뭔가 복잡해진 것 같아서 마음에 크게 들진 않는다.
5) delete
current.data가 '~'인 경우, 맨 앞에 있는 것이기 때문에 지울 수 없다. 따라서 해당 경우 return을 해주었다.
self.current.next가 None이 아닐 경우엔, 삭제 되어야 하는 노드 앞 뒤로 값을 연결해주어야 하기 때문에 해당 경우도 고려해 주었다.
6) print
print의 경우, 처음에 선언한 '~' 노드를 제외한 다른 노드들을 하나씩 출력해주었다.
++ 다른 풀이들을 보아하니, 2개의 stack으로 푸는 것도 좋았을 듯 싶다.
하지만, 이번 주차 문제 풀이가 linked list에 관한 것이어서 이를 이용해 보았다.
2. 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoubleLinkedList:
def __init__(self):
new_node = Node('~')
self.current = new_node
self.head = new_node
def left(self):
if self.current.data == '~':
return
self.current = self.current.prev
def right(self):
if self.current.next is None:
return
self.current = self.current.next
def character(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.current = new_node
return
if self.current.next is None:
self.current.next = new_node
new_node.prev = self.current
self.current = new_node
return
new_node.prev = self.current
new_node.next = self.current.next
self.current.next.prev = new_node
self.current.next = new_node
self.current = self.current.next
def delete(self):
if self.current.data == '~':
return
if self.current.next is not None:
self.current.next.prev = self.current.prev
self.current.prev.next = self.current.next
self.current = self.current.prev
def print(self):
self.head = self.head.next
while self.head is not None:
print(self.head.data,end="")
self.head = self.head.next
print()
for i in range(int(input())):
keylog = DoubleLinkedList()
for char in input():
if char == '>':
keylog.right()
elif char == '<':
keylog.left()
elif char == '-':
keylog.delete()
else:
keylog.character(char)
keylog.print()
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/12] 11725번 트리의 부모 찾기 (1) | 2024.02.12 |
---|---|
[백준 2024/02/11] 1260번 DFS와 BFS (0) | 2024.02.11 |
[백준 2024/02/08] 1094번 막대기 (2) | 2024.02.08 |
[백준 2024/02/08] 11279번 최대 힙 - python ver. (0) | 2024.02.08 |
[백준 2024/02/08] 1927번 최소 힙 - python ver. (0) | 2024.02.08 |