[프로그래머스] 표 편집 (Python)

1. 문제

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

코딩테스트 연습 - 표 편집

2. 풀이

처음에 배열로 풀었다가 효율성에서 걸려서 검색해서 다른 사람의 풀이를 참조했다.

이중 링크드 리스트로 풀어야하는 문제. 

 

1번 인덱스부터 시작하여 처음에 현재위치(cur)을 +1 해주었다.

 

prev와 next의 값을 저장하여 현재위치(cur)을 옮길 때마다 값을 갱신해준다.

 

그리고 삭제하는 경우에는 stack에다가 최근에 삭제한 것을 꺼낼 수 있도록 삭제한 행을 저장한다.

동시에 res 배열에 삭제한 행의 삭제 여부를 갱신하고 마지막에 배열의 최종 결과를 answer로 리턴한다. 

 

3. 코드

def solution(n, k, cmd):
    answer = ''
    linked_list = {i: [i-1, i+1] for i in range(1, n+1)}
    res = ['O'] * (n) #O: 삭제안함, X: 삭제됨
    cur = k
    stack = []
    
    cur+=1
    
    for c in cmd:
        if(len(c)>1):
            tmp = c.split(' ')
            val = int(tmp[1])
            if(tmp[0] == 'D'):
                for _ in range(val):
                    cur = linked_list[cur][1]
            elif(tmp[0] =='U'):
                for _ in range(val):
                    cur = linked_list[cur][0]
        else:
            #선택한 행 삭제
            if c=='C':
                prev, nxt = linked_list[cur]
                stack.append([prev, cur, nxt])
                res[cur-1]='X'
                #마지막 행인 경우
                if nxt == n+1:
                    cur = linked_list[cur][0]
                else:
                    cur = linked_list[cur][1]
                if prev == 0:
                    linked_list[nxt][0] = prev
                elif nxt == n+1:
                    linked_list[prev][1]=nxt
                else:
                    linked_list[prev][1] = nxt
                    linked_list[nxt][0] = prev
                    
            #가장 최근에 삭제한 행 복구
            elif c=='Z':
                prev, now, nxt = stack.pop()
                res[now-1] = 'O'
                
                if prev == 0:
                    linked_list[nxt][0] = now
                elif nxt == n+1:
                    linked_list[prev][1] = now
                else:
                    linked_list[prev][1] = now
                    linked_list[nxt][0] = now
                    
                    
    for x in res:
        answer += x

    return answer

*참고

https://minhyeok-rithm.tistory.com/entry/%ED%91%9C-%ED%8E%B8%EC%A7%91-1

https://ckd2806.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%91%9C-%ED%8E%B8%EC%A7%91