[프로그래머스/PYTHON] 표 편집

프로그래머스 '표 편집'입니다.

 

문제 링크

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

코딩테스트 연습 - 표 편집

---

● 문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

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

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

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

 

제한사항

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
  • cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
  • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
  • X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
  • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
  • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
  • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복 없이 채워져 있다고 가정하고 문제를 해결해 주세요.
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
• 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어 붙인 문자열 형태로 return 해주세요.

정확성 테스트 케이스 제한 사항

• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

● 문제 해결 방향

이 문제는 효율성을 따지는 문제로 막연히 동작만 확인하는 것이 아니라 얼마나 효율적을 문제를 해결하는지도 보는 문제이다. ( 진짜 어렵다.. )

 

문제 자체를 이해하는 것은 어렵지 않았다.

명령어 별로 필요한 요구사항을 작성해주면 된다.

 

C, Z 명령어를 작업할 때 삭제 기록을 따로 저장하여

다시 리스트에 넣을 때 사용할 수 있도록 했다.

 

배열을 사용하기 보다 효율성 측면을 해결하기 위해

Linked-list를 사용하였다.

---

● 문제 해결 코드

def up(current, move, linked_list):
    for _ in range(move):
        pre, post = linked_list[current]
        current = pre
    return current

def down(current, move, linked_list):
    for _ in range(move):
        pre, post = linked_list[current]
        current = post
    return current

def cut(table, k, recent, linked_list):
    table[k] = "X"
    
    pre, post = linked_list[k]
    recent[k] = linked_list.pop(k)
    
    # 삭제 노드가 가장 앞에 있을때 -> 삭제후 가장 마지막 노드를 return
    if pre == None:
        linked_list[post][0] = None
    # 삭제 노드가 가장 뒤에 있을 때
    elif post == None:
        linked_list[pre][1] = None
        return pre
        
    else :
        linked_list[pre][1] = post
        linked_list[post][0] = pre
    
    # 삭제한 노드의 post노드를 return
    return post
        
    
def ctrlz(table, k, recent, linked_list):
    re, re_item = recent.popitem()
    
    table[re] = 'O'
    pre, post = re_item
    
    linked_list[re] = [pre, post]
    
    # 이전 이후 노드를 업데이트, 이때 이전, 이후노드가 None일 경우 Update할 필요가 없다.
    if pre != None :
        linked_list[pre][1] = re
        
    if post != None :
        linked_list[post][0] = re
    
    return

def solution(n, k, cmd):
    
    #배열 내 존재 여부를 나타내는 배열과, 삭제된 기록을 저장하는 dict를 선언
    table = ['O' for i in range(n)]
    recent = {}

    # N개의 링크드 리스트를 선언
    linked_list = {i:[i-1, i +1] for i in range(1, n-1)}
    linked_list[0] = [None, 1]
    linked_list[n-1] = [n-2, None]

    for c in cmd:
        if c[0] == 'U':
            move = int(c.split()[-1])
            k = up(k, move, linked_list)
        elif c[0] == 'D':
            move = int(c.split()[-1])
            k = down(k, move, linked_list)
        elif c[0] == 'C':
            k = cut(table, k, recent, linked_list)
        elif c[0] == 'Z':
            ctrlz(table, k, recent, linked_list)
            
    return ''.join(table)

1. up 함수

이동할 때마다 pre node로 이동한다.

 

2. down 함수

이동할 때마다 post node로 이동한다.

 

3. cut 함수

노드 존재를 알려주는 배열에 해당 노드가 삭제되었음을 반영하고,

 

삭제 노드를 제거한다.

 

만약 삭제노드가 가장 앞에 있는 노드인 경우 다음 노드의 pre 노드를 None으로 바꾼다.

만약 삭제노드가 가장 뒤에 있는 노드인 경우 이전 노드의 post 노드를 None으로 바꾼다.

가장 마지막 노드를 지워줄 경우 삭제 노드의 이전 노드로 인덱스를  이동한다.

 

그리고 삭제노드 이전과 이후 노드를 서로 연결해준다.

 

4. ctrlz 함수

삭제 기록 배열에서 가장 최근의 노드를 뽑아주준다.

 

그리고 노드 존재를 알려주는 배열에 반영한다.

 

그리고 노드의 pre, post에 저장된 노드와 각각 연결해준다.

이때 pre, post 노드가 None일 경우는 연결하지 않는다.

 

그리고 마지막에

노드 존재를 알려주는 노드를 join 하여 return 한다.

 

---

● 알게 된 것

1. . popitem() : pop() 함수와 같은 기능을 dict type에 적용할 수 있는 함수
2. 배열로 해결하는 것보다  linked-list로 접근하는 것이 효율성 측면에서 뛰어나다.
   -> 처음에 배열로 해결했을 때 정확성 측면에서는 전부 맞았으나 효율성에서는 0점...