[Programmers][Python]표 편집
https://programmers.co.kr/learn/courses/30/lessons/81303?language=python3
📌풀이
내가 쓴 풀이(실패)
- 리스트의 인덱스를 활용하여 구현
C
의 경우,O
이 나올때까지 현재 위치에서 뒤로 밀다가 없으면 앞쪽에서 찾는 방식 활용- 사라진 인덱스는
trash
에 저장 - 해당 인덱스의
table
값은X
로 변경
- 사라진 인덱스는
Z
의 경우,trash
에 저장한 인덱스를 꺼내table
의 값을O
로 변경U
,D
의 경우,X
인 경우를 배제하고 움직이는 횟수를 활용하여 구현- 정확도는 통과하였으나, 효율성에서 5개의 테스트 케이스만 통과
def solution(n, k, cmd):
table = ['O' for _ in range(n)]
trash = []
for c in cmd :
if c == 'C':
trash.append(k)
table[k] = 'X'
# k 위치 변경
while k < n and table[k] == 'X' :
k += 1
if k == n:
k -= 1
while 0 <= k and table[k] == 'X':
k -= 1
elif c == 'Z':
table[trash.pop()] = 'O'
else:
flag = 1 if c[0] == 'D' else 0
move, cnt = int(c[2:]), 0
while cnt < move :
k = k+1 if flag else k-1
if table[k] == 'O':
cnt += 1
return ''.join(table)
내가 쓴 풀이(성공)
- 링크드 리스트 활용
- 딕셔너리의 key를 인덱스값으로, value를 [앞의 값, 뒤의 값] 의 쌍으로 구현
C
의 경우, 해당 인덱스를trash
에 저장- 결과값도
X
로 변경 - 앞의 노드와 뒤의 노드를 연결
- 현재 노드가 맨 앞, 맨 뒤인 경우를 고려하며,
k
값도 맞춰서 이동
- 결과값도
Z
의 경우,trash
에서pop
- 결과값
O
로 변경 - 꺼내온 노드의 위치를 파악하여 사이에 넣고 연결
- 결과값
U
,D
의 경우, 이전, 이후 값들을 보며 노드를 횟수만큼 이동
def solution(n, k, cmd):
res = ['O' for _ in range(n)]
linked_list = {i:[i-1,i+1] for i in range(n)}
trash = []
for c in cmd:
now = c[0]
if now == 'D':
move = int(c[2:])
for _ in range(move):
k = linked_list[k][1]
elif now == 'U':
move = int(c[2:])
for _ in range(move):
k = linked_list[k][0]
elif now == 'C':
pre,nex = linked_list[k][0], linked_list[k][1]
trash.append(k)
res[k] = 'X'
if pre >= 0:
linked_list[pre][1] = nex
if nex < n :
linked_list[nex][0] = pre
k = nex
else :
k = pre
else :
now = trash.pop()
res[now] = 'O'
pre, nex = linked_list[now][0], linked_list[now][1]
if pre >= 0 :
linked_list[pre][1] = now
if nex < n:
linked_list[nex][0] = now
return ''.join(res)
📌후기
링크드 리스트를 쉽게 구현할 수 있는 방법을 알았던 문제였다. 문제를 해결하는 동안, 정말 많은 시간이 소요되었지만 링크드 리스트 활용법을 알게 되었다는 점은 상당히 만족스럽다. 이전에 링크드 리스트를 활용할 때는 객체를 직접 만들어 활용하였는데, 간단한 경우 딕셔너리를 통해 쉽게 만들 수 있다는 것을 알게 되었다! 효율성과 같은 문제에서 자주 활용할 수 있을 것이라고 생각한다.
카카오 테크 블로그의 풀이를 보면서, Fenwick Tree를 활용하여 문제를 해결할 수 있다는 것도 읽었는데, 아직 그 방법에 대해서는 잘 모르겠다. 한번 연구해 봐야 겠다!
Author And Source
이 문제에 관하여([Programmers][Python]표 편집), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mein-figur/ProgrammersPython표-편집저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)