[프로그래머스] 표편집

문제

• 표의 행을 선택, 삭제, 복구하는 프로그램을 만들어야 한다.
  • "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
  • "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
  • "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
  • "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
• 처음 표의 상태에서 모든 명령어를 수행한 후 표의 상태를 비교해 삭제되지 않은 행은 O, 삭제된 행은 X로 표시해 문자열의 형태로 리턴하기
• 제한사항
  • 5 <= 표의 크기 <= 1,000,000 
  • 1 <= 명령어 개수 <= 200,000

 

풀이

• 명령어의 개수가 최대 200,000개 이므로 1초내 실행이라고 생각하면 200개 연산 안에 해결되어야 한다. 그런데 표의 크기는 최대 1,000,000개다.
  • U/D 명령어에서 하나씩 이동할 수 없다.
  • C/Z 명령어에서 행을 삭제하고 복구할 때 빠르게 해결해야 한다.
• 각 행 번호를 리스트로 해서 U/D 명령어를 $O(1)$ 에 해결하고, C/Z 명령어를 $O(k)$에 해결하려고 했지만, 실패
  • Z 명령어에서 행 복구할 때 정확한 위치로 복구되지 않음
  • 효율성 테스트 통과 못하는 것을 보니 U/D 명령어보다 C/Z 명령어가 많은가 보다.
• 링크드 리스트로 구성해 U/D 명령어를 $O(n)$에 해결하고, C/Z 명령어를 $O(1)$ 에 해결하려고 시도, 성공!
  • nums[k] : [ 앞 번호, 뒷 번호] 를 dictionary 형태로 갖는다.
  • U/D의 경우 현재 선택된 행 k 값에서 앞 번호로 또는 뒷 번호로 반복해서 이동한다.
  • C의 경우 선택 행의 링크를 끊어 이동시킨다. (링크드 리스트와 동일) K 값도 다음 행으로 이동시켜준다.
  • Z의 경우 최근 삭제된 행의 링크를 복구시킨다. (링크드 리스트와 동일)

 

from collections import deque

def solution(n, k, cmd):
    nums = {i: [i - 1, i + 1] for i in range(n)}    # LinkedList
    deletes = []                                    # 삭제 스택
    answer = ['O'] * n                              # 행 별 삭제된 행과 삭제되지 않은 행 판별
    
    for c in cmd: 
        c = c.split()
        if c[0] == "U" :       # 윗칸 선택 (링크 앞으로)
            for _ in range(int(c[1])):
                k = nums[k][0]
        elif c[0] == "D" :     # 아랫칸 선택 (링크 다음으로)
            for _ in range(int(c[1])):
                k = nums[k][0]
        elif c[0] == "C" :     # 선택행 삭제 후 바로 아래행 선택
            prev, nxt = nums[k]
            deletes.append((prev, k, nxt))
            answer[k] = 'X'
            
            if prev != -1 : # 맨 앞의 데이터를 삭제한 경우
                nums[prev][1] = nxt
            if nxt != n :	# 맨 뒤의 데이터를 삭제한 경우
                nums[nxt][0] = prev
            
            k = nums[k][0] if nxt == n else nums[k][1]	# 다음 행 선택
        
        elif c[0] == "Z" :
            prev, idx, nxt = deletes.pop()  # 삭제 스택에서 추출    
            answer[idx] = 'O'
            
            if prev != -1 :	# 맨 앞으로 데이터를 추가한 경우
                nums[prev][1] = idx
            if nxt != n :	# 맨 뒤로 데이터를 추가한 경우
                nums[nxt][0] = idx
    
    return ''.join(answer)

 

References

• 프로그래머스 Lv3 표편집