오늘은 2021 카카오 채용연계형 인턴십 문제인 표 편집을 풀어보았다.
1. 문제 설명
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다.
위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다."D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다."C": 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다."Z": 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).
다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.
다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.
다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.
위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.
다시한번 "Z"를 수행하면 그 다음으로 최근에 제거된 "콘"이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.
이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.
처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
2. 나의 풀이
def solution(n, k, cmd):
# 최종 결과를 위해 'O/X' 업데이트
answer = {}
for i in range(n):
answer[i] = 'O'
# 지운 순서대로 넣어두는 것
redo = []
# row number
row = [i for i in range(n)]
for c in cmd:
action = c.split(' ')[0]
if action == 'D':
k += int(c.split(' ')[1])
elif action == 'U':
k -= int(c.split(' ')[1])
elif action == 'C':
redo.append([k,row[k]])
answer[row[k]] = 'X'
del row[k]
if k == len(row):
k = len(row) - 1
elif action == 'Z':
ins = redo.pop()
row.insert(ins[0], ins[1])
answer[ins[1]] = 'O'
if ins[0] <= k:
k += 1
return ''.join(list(answer.values()))결과는 정확성 테스트는 모두 통과했지만 효율성 테스트를 통과하지 못했다. 문제는 n이 최대 1,000,000이고 cmd는 최대 200,000이므로 배열로 풀게되면 효율성 테스트를 통과하지 못한다. 검색해보니 heap 또는 더블 링크드 리스트로 푼 경우가 많았다. 추후 새롭게 구현해서 다시 풀어볼 예정.
def solution(n, k, cmds):
nodes = {0: [n-1, 1]}
for i in range(1, n):
if i == n-1:
nodes[i] = [i-1, 0]
else:
nodes[i] = [i-1, i+1]
redo = []
for cmd in cmds:
action = cmd.split(' ')[0]
if action == 'D':
x = int(cmd.split(' ')[1])
while x > 0:
k = nodes[k][1]
x -= 1
elif action == 'U':
x = int(cmd.split(' ')[1])
while x > 0:
k = nodes[k][0]
x -= 1
elif action == 'C':
nodes[nodes[k][0]][1] = nodes[k][1]
nodes[nodes[k][1]][0] = nodes[k][0]
redo.append([k, nodes[k]])
tmp = nodes[k]
del nodes[k]
if tmp[1] == 0:
k = tmp[0]
else:
k = tmp[1]
else:
curr_node, val = redo.pop()
prev_node, next_node = val
nodes[curr_node] = [prev_node, next_node]
nodes[prev_node][1] = curr_node
nodes[next_node][0] = curr_node
answer = ''
for i in range(n):
if nodes.get(i) is None:
answer += 'X'
else:
answer += 'O'
return answer혼자서는 잘 못 풀겠어서 다른 블로그를 참고하여 코드를 작성해보았다. 더블링크드 리스트를 어떻게 활용하는 것인지 감을 잡을 수 있었고 다음에는 도움없이 직접 알고리즘을 작성해보는 연습을 해야겠다.
3.다른 풀이
import heapq
def solution(n, k, cmds):
answer = ''
def inverse(num):
return -num
max_heap = list(map(inverse,range(k)))
min_heap = list(range(k,n))
deleted = ['O' for _ in range(n)]
deleted_stack = []
heapq.heapify(max_heap)
heapq.heapify(min_heap)
for cmd in cmds:
command = cmd.split()
if len(command)>1:
num = command[1]
command = command[0]
num = int(num)
if command == 'D':
for _ in range(num):
heapq.heappush(max_heap,-heapq.heappop(min_heap))
else:
for _ in range(num):
heapq.heappush(min_heap,-heapq.heappop(max_heap))
else:
command = command[0]
if command == 'C':
delete_num = heapq.heappop(min_heap)
deleted_stack.append(delete_num)
deleted[delete_num] = 'X'
if len(min_heap) == 0:
heapq.heappush(min_heap,-heapq.heappop(max_heap))
else:
restore_num = deleted_stack.pop()
deleted[restore_num] = 'O'
if min_heap[0] > restore_num:
heapq.heappush(max_heap,-restore_num)
else:
heapq.heappush(min_heap,restore_num)
answer = ''.join(deleted)
return answer힙을 활용한 풀이를 가져와봤다.
