프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
문제
https://programmers.co.kr/learn/courses/30/lessons/81303
내가 작성한 코드
class node:
def __init__(self, x=-1, l=None, r=None):
self.x = x
self.l = l
self.r = r
def pop(l, r):
if l:
l.r = r
if r:
r.l = l
return r or l
def insert(n, l ,r):
if l:
l.r, n.l = n, l
if r:
r.l, n.r = n, r
def solution(n, k, cmd):
answer = []
stk = []
head = node()
now = None
crnt = head
for i in range(n):
nw_node = node(i, crnt)
crnt.r, crnt = nw_node, nw_node
if i == k:
now = crnt
for c in cmd:
if c[0] == "U":
for _ in range(int(c.split()[1])):
now = now.l
elif c[0] == "D":
for _ in range(int(c.split()[1])):
now = now.r
elif c[0] == "C":
stk.append((now, now.l, now.r))
now = pop(now.l, now.r)
elif c[0] == "Z":
insert(*stk.pop())
crnt = head
for i in range(n):
if crnt.r and crnt.r.x == i:
answer.append('O')
crnt = crnt.r
else:
answer.append('X')
return ''.join(answer)
- 연결리스트
- 각 인덱스 값을 가진 연결리스트로 명령 수행
- 수행이 끝나고 전체 탐색하여 인덱스와 일치하는 값이 위치에 없는 경우 X 삽입
다른 사람이 작성한 코드
def solution(n, k, cmd):
answer = ''
linked_list = {i: [i - 1, i + 1] for i in range(1, n+1)} #n=8일때 1~8까지
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)
- 연결리스트 문제라는 것을 이 분의 설명을 통해 깨달았다
기억해야할 것
- 연결리스트의 힌트
- 인덱스를 사용하지 않고 위/아래로 움직임
- 배열의 중간 요소에 대한 제거/삽입이 빈번함
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_인턴][2021] 시험장 나누기 (0) | 2021.09.05 |
---|---|
[프로그래머스][KAKAO_인턴][2021] 미로 탈출 (0) | 2021.09.05 |
[프로그래머스][KAKAO_인턴][2021] 거리두기 확인하기 (0) | 2021.09.05 |
[프로그래머스][KAKAO_인턴][2021] 숫자 문자열과 영단어 (0) | 2021.09.05 |
[프로그래머스][KAKAO_BLIND][2018] 자동 완성 (0) | 2021.09.03 |