2021 카카오 인턴십 문제 3번 : 표 편집
규칙에 맞게 표편집을 한 뒤에 처음과 비교하여 결과를 출력하는 문제
문제설명
규칙은 아래와 같습니다.
- "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
- "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
- "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
- "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
표는 아래와 같이 왼쪽에 행번호가 0부터 시작됩니다. 표에서 수정이 일어나면 행번호는 그에 맞게 바뀌어야합니다. 하지만 마지막에는 결국 처음과 비교해서 삭제여부를 판단해야하기때문에 식별을 해줘야하는 상황입니다.
실제 입력은 이름과 같은 정보는 주어지지 않고 커서를 움직이며 행을 삭제를 하고 복구하고가 반복됩니다.
풀이1. 삭제여부기록하기
일단 어떤 자료구조를 통해서 구현할 것인지를 정해야하는데 두가지가 생각났습니다. 하나는 배열 다른 하나는 연결리스트입니다. 처음에는 그냥 배열로 구현하고 각각 삭제여부를 표시해주기로 했습니다. 마지막에 결국 비교해야하는 것은 삭제 여부이니까요!
li = [True] * n위아래 커서 움직이기
일단 이 액션이 가장 난이도가 쉬울 것으로 예상되었습니다. k에 커서 인덱스가 주어지기 때문에 k의 값을 변경하는 것으로 구현하면 될 것입니다. 그런데 저는 삭제여부로 기록하였기 때문에 False인 행들은 건너뛰면서 X만큼 움직여야합니다. 그부분만 조심하면 쉽게 구현할 수 있을 것 같습니다.
삭제
이렇게하면 삭제후에 맨마지막을 복구해야하기 때문에 휴지통(trashcan)을 스택으로 구현해놨습니다. 따라서 해당행의 상태를 False로 만들어주고 휴지통에 해당 인덱스만 넣어주면 됩니다. 근데 살짝 문제는 삭제후 커서의 위치를 정하는 것입니다.
이부분은 먼저 밑으로 내려가면서 가장 처음으로 True인 위치를 찾습니다. 만약 끝까지 없다면 다시 현재위치를 기준으로 위로 올라가면서 가장 처음으로 True인 위치를 찾습니다.
복구
복구는 간단히 trashcan에서 pop한 인덱스를 True로 만들어주면 됩니다.
코드
# 정확성 통과
def solution(n, k, cmd):
li = [True] * n
trashcan = []
for c in cmd:
c = c.split()
if c[0] == "D":
cnt = 0
while cnt < int(c[1]):
k += 1
if li[k]:
cnt += 1
elif c[0] == "U":
cnt = 0
while cnt < int(c[1]):
k -= 1
if li[k]:
cnt += 1
elif c[0] == "C":
li[k] = False
trashcan.append(k)
# 아래로 찾기
p = k + 1
while p < n and not li[p]:
p += 1
# 끝에 도달 했으면
if p >= n:
# 위로 찾기
p = k - 1
while p > -1 and not li[p]:
p -= 1
k = p
else:
li[trashcan.pop()] = True
answer = ""
for i in li:
if i:
answer += "O"
else:
answer += "X"
return answer
이렇게 하면 안타깝게도 효율성에서 4문제가 시간초과를 하게됩니다!
문제점 파악
어디가 병목구간일까요..?
예측가는 지점은 앞뒤를 기록하지 않았기 때문에 False를 건너뛰면 매번 연결관계를 찾아나가야하는 부분들입니다. n이 작다면 문제가 없겠지만 n이 최대 1,000,000이라는 점을 고려하면 False가 많아질수록 실제 앞, 뒤 관계를 찾는데에 시간이 많이 들 것으로 보입니다.
풀이2 : +앞뒤관계기록하기
그럼 앞뒤 관계를 기록해서 저 부분의 시간을 단축하면 될 것 같습니다. 따라서 각각의 앞뒤 인덱스를 저장해주는 것으로 바꿨습니다.
li = [[True, i - 1, i + 1] for i in range(n)]n이 5일때는 아래와 같은 초기값을 가집니다. 양끝은 -1, n으로 들어가게 됩니다.(유효성체크가필요하겠네요!)
[[True, -1, 1], [True, 0, 2], [True, 1, 3], [True, 2, 4], [True, 3, 5]]위아래 커서 움직이기
일단 이부분은 훨씬 간단해졌습니다. 현재 위치에서 앞, 뒤 인덱스로 X번만큼 이동해주면 끝입니다.
삭제
삭제는 꼭 연결리스트를 삭제할 때 처럼 관계를 새로이어주고 빠지면 됩니다. 빠지는 것은 False로 그리고 관계는 내 앞을 나의 뒤와 내 뒤를 나의 앞과 이어주면 되겠습니다. 이때 내 앞이나 뒤가 -1이나 n과 같이 범위 밖의 인덱스일 수 있으니 유효성체크를 해줘야합니다.
커서는 내 뒤가 유효하면 뒤로 그렇지않으면 앞으로 옮기면 됩니다
복구
사실 이게 이 문제의 핵심이라고 생각합니다. 복잡해보일 수 있지만 사실 복구를 최근 것부터 한다는 이 순서도 중요한 부분입니다.
만약 중간에 두개가 차례대로 삭제된 상태라면 아래와 같은 상태일 것입니다.
이때 복구를 한번 하게 되면 복구된 노드의 앞과 뒤가 자신을 가르키도록 바꾸면 됩니다. 삭제 된 노드는 앞뒤를 기록하고있었고 최근 것 부터 복구되기 때문에 가능한일입니다.
최종코드
# 효율성 통과
def solution(n, k, cmd):
li = [[True, i - 1, i + 1] for i in range(n)]
trashcan = []
def is_valid(num):
if 0 <= num <= n - 1:
return True
return False
for c in cmd:
c = c.split()
if c[0] == "D":
for i in range(int(c[1])):
k = li[k][2]
elif c[0] == "U":
for i in range(int(c[1])):
k = li[k][1]
elif c[0] == "C":
li[k][0] = False
trashcan.append(k)
# 이어주기
if is_valid(li[k][1]):
li[li[k][1]][2] = li[k][2]
if is_valid(li[k][2]):
li[li[k][2]][1] = li[k][1]
if is_valid(li[k][2]):
k = li[k][2]
else:
k = li[k][1]
else:
rc = trashcan.pop()
li[rc][0] = True
# 다시이어주기
if is_valid(li[rc][1]):
li[li[rc][1]][2] = rc
if is_valid(li[rc][2]):
li[li[rc][2]][1] = rc
answer = ""
for i in li:
if i[0]:
answer += "O"
else:
answer += "X"
return answer```