[프로그래머스][level3] 표 편집 -python

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

문제 풀이 - 다른 블로그 참고

• 이중 연결 리스트 사용. 이중 연결 리스트 직접 사용해본 적은 처음인 듯 .. 

def solution(n, k, cmd):
  answer = ''

  # 이중 연결 리스트 
  # 표의 위치별 이전 표와 다음 표 기록 
  linked_list = { i : [i-1, i+1] for i in range(n)}
  
  # 현재 가리키고 있는 위치 
  cursor = k 
  
  # 삭제된 표 정보 기록할 리스트 
  delete = []
  
  # 삭제 여부 기록할 리스트 
  state = ["O"] * n

  # 명령마다 
  for i in cmd:
    
    if len(i) > 1 :
      # 명령어와 칸 구분 
      s, num = i.split()
      num = int(num)
      
      # 다음 칸으로 이동 
      if s == 'D':  
        # 입력된 칸 수만큼 
         for _ in range(num):
          cursor = linked_list[cursor][1]

     # 이전 칸으로 이동 
      elif s == 'U':
        # 입력된 칸 수 만큼 
        for _ in range(num):
          cursor = linked_list[cursor][0]
    
    else :
      # 삭제 명령
      if i == 'C':
        # 이전 칸, 다음 칸 위치 기록 
        prev, nex = linked_list[cursor]
        # 삭제된 표 정보 기록 
        delete.append((prev,cursor,nex))
        # 삭제 정보 갱신 
        state[cursor] = 'X'
        
        # 맨 마지막 칸이 삭제되었다면 
        if nex == n:
          # 커서 이전 칸으로 이동 
          cursor = linked_list[cursor][0]
        else:
          # 커서 다음 칸으로 이동 
          cursor = linked_list[cursor][1]

        # 맨 앞 칸이 삭제 되었다면 
        if prev == -1:
          # 다음 칸의 이전 칸 정보만 갱신 
          linked_list[nex][0] = prev
        # 맨 마지막 칸이 삭제 되었다면 
        elif nex == n :
          # 이전 칸의 다음 칸 정보만 갱신 
          linked_list[prev][1] = nex
       # 중간에 있는 칸이 삭제 되었다면 
        else:
          # 이전 칸과 다음 칸의 정보 갱신 
          linked_list[prev][1] = nex
          linked_list[nex][0] = prev

      # 복구 명령 
      else:
        # delete 리스트에서 최근에 기록된 정보 pop 
        prev, now, nex = delete.pop()
        # 삭제 여부 갱신
        state[now] = 'O'

        # 맨 처음 칸이었다면 
        if prev == -1:
          linked_list[nex][0] = now
        # 맨 마지막 칸이었다면 
        elif nex == n:
          linked_list[prev][1]= now
        else :
          linked_list[prev][1]= now
          linked_list[nex][0] = now

  for x in state:
    answer += x 

  return answer

+ 2022.04.25 다시 풀이

- state에 현재 상태를 기록해두고 하나씩 확인해가며 검사해주니깐 시간 초과 

# 효율성 검사 시 시간초과 발생 
from collections import deque

def solution(n, k, cmd):
    state = ['O'] * n
    # 삭제된 인덱스 번호 저장 
    q = deque()
    for s in cmd :
        s = s.split()
        
        # X칸 아래 
        if s[0] == 'D':
            cnt = 0 
            while cnt < int(s[1]):
                k += 1 
                if state[k] == 'O':
                    cnt += 1 
        # X칸 위 
        if s[0] == 'U':
            cnt = 0 
            while cnt < int(s[1]):
                k -= 1 
                if state[k] == 'O' :
                    cnt += 1 
        # 현재 행 삭제 
        if s[0] == 'C':
            # 삭제 
            state[k] = 'X'
            q.append(k)
            if k == n-1:
                # 한 칸 위로 이동 
                while True :
                    k -= 1 
                    if state[k] == 'O':
                        break 
            else :
                # 한 칸 밑으로 이동 
                while True :
                    k += 1 
                    if state[k] == 'O':
                        break 

        # 가장 최근에 삭제된 행 원래대로 복구 
        if s[0] == 'Z':
            num = q.pop()
            state[num] = 'O'
        
    return "".join(state)
    
n = 8
k = 2
cmd = ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]
print(solution(n,k,cmd))

- 연결 리스트로 풀었다. 

connect 에 index 별 가리키고 있는 이전 노드, 다음 노드 번호 저장 

큐에 삭제된 node 번호 저장 

 

계속해서 테스트 케이스 21번, 효율성 7번에서 틀렸다고 해서 도대체 뭐지 했는데 

맨 뒤에꺼 삭제 조건을 k == n-1, 맨 앞께서 삭제 조건을 k == 0 이라고 해서 그런거였다

이전 가리키는 노드나 다음 가리키는 노드가 -1 일 때 맨앞, 맨뒤 ! 

from collections import deque

def solution(n, k, cmd):
    # 삭제된 인덱스 번호 저장 
    q = deque()
    # 인덱스 별 상태 저장 
    answer = ['O'] * n
    # 인덱스 별 가리키고 있는 이전 노드, 다음 노드 번호 저장 
    connect = []
    
    for i in range(n-1):
        connect.append([i-1, i+1])
        
    # 맨 앞, 맨 뒤 일 경우 -1 가리키고 있게 함 
    connect.append([n-2,-1])
    
    for s in cmd :
        s = s.split()
        
        # X칸 아래 
        if s[0] == 'D':
            for _ in range(int(s[1])):
                k = connect[k][1]
                
        # X칸 위 
        if s[0] == 'U':
            for _ in range(int(s[1])):
                k = connect[k][0]
                
        # 현재 행 삭제 
        if s[0] == 'C':
            # 삭제 상태로 변경 
            answer[k] = 'X'
            # 큐에 삭제 인덱스 번호 저장 
            q.append(k)
            
            pre = connect[k][0]
            next = connect[k][1]
            # 가장 마지막 꺼 삭제 
            if next == -1 :
                connect[pre][1] = -1 
                k = pre
            # 가장 앞에꺼 삭제 
            elif pre == -1 :
                connect[next][0] = pre
                k = next 
            else :
                connect[pre][1] = next 
                connect[next][0] = pre
                k = next 

        # 가장 최근에 삭제된 행 원래대로 복구 
        if s[0] == 'Z':
            num = q.pop()
            answer[num] = 'O'
            pre = connect[num][0]
            next = connect[num][1]
            
            # 가장 뒤에꺼 복구 
            if next == -1 :
                connect[pre][1] = num
            # 가장 앞에꺼 복구 
            elif pre == -1 :
                connect[next][0] = num
            # 사이에 있는 거 복구 
            else :
                connect[next][0] = num
                connect[pre][1] = num
                
            
    return "".join(answer)

n = 8
k = 2
cmd =["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]
print(solution(n,k,cmd))