프로그래머스 - 표 편집

프로그래머스 - 표 편집

효율성 3개 통과 못함 ㅠㅠ

명령어의 종류

• 행 선택
• 행 삭제
• 행 복구

명령어

• U X : 현재 선택된 행에서 X칸 만큼 위에 있는 행을 선택
• D X : 현재 선택된 행에서 X칸 만큼 아래에 있는 행을 선택
• C : 현재 선택된 행 삭제 후, 바로 아래 행 선택. 만약 삭제된 행이 가장 마지막 행일 경우 바로 윗행을 선택
• Z : 가장 최근에 삭제된 행을 복구. 선택된 행은 바뀌지 않음

---

문제 핵심

1. 명령어를 실행한다.

2. 삭제되지 않은 행은 'O', 삭제된 행은 'X'로 표시하여 문자열로 만들어준다.

• C 명령어에서 삭제할 행이 마지막 행인 경우 예외처리
• 행 번호보다는 현재 선택되어 있는 행이 몇번째 행인지 기억하는게 중요할듯
• 행이 삭제된 후, 테이블에 존재하는 행의 개수(테이블의 크기)도 기억하기

---

문제 풀이

• 삭제 혹은 복구 될 행들을 저장할 stack
• U X : 현재 선택된 k 행 - X
• D X : 현재 선택된 k 행 + X
• C : 삭제 후, k = k 혹은 k -= 1
• Z : 복구 후, 복구된 행이 현재 선택된 행보다 앞에 존재하거나 같을경우, k += 1

---

초기 상태

• n = 8
• k = 2
• cmd = ["D 2" , "C" , "U 3" , "C" , "D 4" , "C" , "U 2" , "Z" , "Z"]
• tableSize = n
• stack = [ ]
  

명령어 ( D 2 )

• 현재 가리키는 행 k = 2
• k = k + 2 = 4
• cmd = [ "C" , "U 3" , "C" , "D 4" , "C" , "U 2" , "Z" , "Z"]
• tableSize = n
• stack = [ ]

명령어 ( C )

• 현재 k = 4
• k = 4
• cmd = ["U 3" , "C" , "D 4" , "C" , "U 2" , "Z" , "Z"]
• tableSize = n - 1 = 7
• stack = [ 4 ]

k 는 tableSize보다 작으므로 마지막 행이 아님

삭제할 행을 stack 에 넣지만, k 의 값은 변하지 않음

명령어 ( U 3 )

• 현재 k = 4
• k = k - 3 = 1
• cmd = ["C" , "D 4" , "C" , "U 2" , "Z" , "Z"]

명령어 ( C )

• 현재 k = 1
• stack = [ 4 , 1 ]
• tableSize = tableSize - 1 = 6
• cmd = ["D 4" , "C" , "U 2" , "Z" , "Z"]

k 는 tableSize보다 작으므로 마지막 행이 아님

삭제할 행을 stack 에 넣지만, k 의 값은 변하지 않음

명령어 ( D 4 )

• 현재 k = 1
• k = k + 4 = 5
• cmd = [ "C" , "U 2" , "Z" , "Z"]

명령어 ( C )

• 현재 k = 5
• stack = [ 4 , 1 , 5 ]
• tableSize = tableSize - 1 = 5
• cmd = ["U 2" , "Z" , "Z"]

삭제되는 행이 마지막 행이고, k는 마지막 행을 가리키고 있으므로 k -= 1

• k = 5 -> k = 4

명령어 ( U 2 )

• 현재 k = 4
• k -= 2
• k = 4 -> k = 2
• cmd = [ "Z" , "Z"]

명령어 ( Z )

• k = 2
• stack = [4,1,5] -> stack = [4,1]
• tableSize += 1 -> tableSize = 6
• cmd = ["Z"]

stack에서 꺼낸 5 행은 현재 k 가 가리키고 있는 행의 뒤에 존재하므로 k의 값은 그대로 유지

명령어 ( Z )

• k = 2 - > k = 3
• stack = [4,1] -> stack = [4]
• tableSize += 1 -> tableSize = 7

stack에서 꺼낸 1행은 현재 k 가 가리키고 있는 행의 앞에 존재하므로 k += 1

왜 앞에 존재하면 k += 1?

k보다 앞에 존재하는행이 복구된다면 k가 가리키는 행이 한칸 뒤로 밀려나게 되기 때문

---

O X 처리

최종적으로 모든 명령을 마치고 stack 에는 복구되지 않은 행들이 저장되어 있다.
(현재는 최종적으로 4번행만 삭제된 상태)

복구되지 않은 행들을 제외하고 나머지 행들은 모두 복구가 된 상태

현재 테이블에 존재하는 행들은 모두 "O" 처리

answer = "O" * tableSize

stack에 남아있는 행들을 순서대로 table에 넣어주면서 들어간 위치에 "X" 처리

 while stack:
        item = stack.pop()
        answer = answer[:item] + "X" + answer[item:]

그림으로 표현하자면 ...

---

풀이 코드:

from collections import deque

def solution(n, k, cmd):
    stack = deque()
    tableSize = n

    for i in range(len(cmd)):
        tmp = cmd[i].split(" ")
        if tmp[0] == "D": # down
            k += int(tmp[1])
        elif tmp[0] == "U": # up
            k -= int(tmp[1])
        elif tmp[0] == "C": # del
            stack.append(k)
            tableSize -= 1
            # 마지막 행이 삭제된 경우 tableSize == k 같아지므로
            if k == tableSize:
                k -= 1
        elif tmp[0] == "Z": # 복구
            index = stack.pop()
            tableSize += 1
            # k 앞에 추가된 경우 k+=1, 뒤일경우 k
            if k >= index:
                k += 1
    answer = "O" * tableSize
    
    while stack:
        item = stack.pop()
        answer = answer[:item] + "X" + answer[item:]
        
    
    return answer

효율성 문제

기존에 존재하는 테이블에서 행을 삭제하고 복구하는 과정은

실제로 행을 삭제하거나 다시 복구(추가)하는것이 아니라 삭제할 때의 행 번호를 stack에 담는 원리이기 때문에 시간복잡도에서 큰 문제는 발생하지 않는다.

최종적으로 stack에 남아 복구되지 않은 행들을 "X" 처리할때에 문자열 인덱스 슬라이싱을 사용한다.

stack에 남아있는 행이 많고, 테이블에도 많은 행들이 존재할경우,
pop, 인덱스 슬라이싱 을 하는 과정에서 시간복잡도가 O(n2)까지 올라가기 때문에 시간초과가 발생한다.

이 문제를 해결하려면 아래와 같은 정보를 가지고

• 초기 테이블에 존재할때의 행 번호 정보
• 변한 테이블에서 존재할때의 행 번호 정보

answer = ["O"] * n
while stack:
    answer[stack.pop()] = "X"

요런식으로 값을 구해야할듯 !
해보려 했는데 결국 못했따
리타이어! ㅜㅠ