Programmers - 표 편집 [Python3] #연결리스트

문제 링크

📄 문제 설명

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다.

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X" : 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X" : 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2" 를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C" 를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X 로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

문제 풀이

1. 연결 리스트 활용

✅ 연결 리스트 정의

class Node :
    def __init__(self, prev = None, next = None):
        self.remove = False
        self.prev = prev
        self.next = next

2. 명령어 읽기

• 위 / 아래 이동: prev 와 next 를 이용해서 이동
• 삭제 : 스택에 cur(현재 노드) 저장 후, cur의 remove를 True로 설정. cur 기준 prev 와 next 를 연결
• 되돌리기: 스택에서 pop()을 통해 최근 삭제한 노드 꺼내서 삭제 전 prev next 와 각각 연결

3. remove로 결과값 (answer) 구하기

노드를 처음부터 돌면서 remove 가 False일 경우에는 리턴값에 'O'를,
True일 경우에는 'X'를 붙인다.

👩🏻‍💻 전체 코드

class Node :
    def __init__(self, prev = None, next = None):
        self.remove = False
        self.prev = prev
        self.next = next
        
def solution(n, k, cmd):
    answer = ""
    chart = [Node(i-1, i+1) for i in range(n)]
    chart[0].prev = None
    chart[n-1].next = None
    removed = []
    cur = k
    
    for c in cmd:
        x = c.split(" ")
        if x[0] == "U":
            for _ in range(int(x[1])):
                cur = chart[cur].prev
        elif x[0] == "D":
            for _ in range(int(x[1])):
                cur = chart[cur].next
        elif x[0] == "C":
            removed.append(cur)
            chart[cur].remove = True
            p , n = chart[cur].prev, chart[cur].next
            
            if p != None:   # if p 로만 조건문을 하면 p가 0일 경우(맨처음index)를 체크하지 못함!
                chart[p].next = n
            if n:
                chart[n].prev = p
                cur = n
            else:
                cur = p
            
        else:
            restore = removed.pop()
            chart[restore].remove = False
            p , n = chart[restore].prev, chart[restore].next
            if p:
                chart[p].next = restore
            if n:
                chart[n].prev = restore
            
    for x in chart:
        if x.remove == False:
            answer += 'O'
        else:
            answer += 'X'
    
    return answer

참고

https://school.programmers.co.kr/questions/35448