[프로그래머스/Python] Level 3_표 편집

📌문제 유형

2021 카카오 채용연계형 인턴십 

 

📌문제

프로그래머스

 

 

📌나의 문제풀이

- 정확성 모두 통과, 효율성 0

def move_UD(idx,d,answer):
    dirs, num = d.split()
    num = int(num)
    rows_num = [n for n,state in answer.items() if state != 'X']
    
    while True:
        if dirs == 'U':
            return rows_num[rows_num.index(idx) - num]
        else:
            return rows_num[rows_num.index(idx) + num]


def move_C(idx,answer):
    # 현재 선택된 행 삭제
    # 최근 삭제된 행도 기억해야 함
    list_ = [n for n,state in answer.items() if state != 'X']
    answer[idx] = 'X'
    
    # 맨 끝인 경우, 바로 윗행 선택
    if idx == list_[-1]:
        return list_[-2], idx
    # 맨 끝 아닌 경우, 바로 다음 행 선택
    else:
        return list_[list_.index(idx) + 1], idx

def move_Z(del_list, answer):
    answer[del_list[-1]] = 'O'
    
    
def solution(n, k, cmd):
    ans = ['O' for _ in range(n)]
    table = [i for i in range(n)]   # 초기 테이블 번호
    answer = dict([(a,b) for a,b in zip(table,ans)])
    del_ = []
    now_idx, del_idx = k, -1   # 현재 위치, 최근 삭제한 위치
    
    for com in cmd:
        if com[0] == 'U' or com[0] == 'D':
            now_idx = move_UD(now_idx,com,answer)
        elif com[0] == 'C':
            now_idx, del_idx = move_C(now_idx,answer)
            del_.append(del_idx)
        else:
            move_Z(del_,answer)
            del_ = del_[:-1]
    # print(answer)
    return ''.join(answer.values())

 

 

📌다른사람의 문제풀이

- Linked list 사용

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

def solution(n, k, cmd):
    cur = k
    table = { i:[i - 1, i + 1] for i in range(n) }
    answer = ['O'] * n
    table[0] = [None, 1]
    table[n - 1] = [n - 2, None]
    stack = []
    for c in cmd:
        if c == "C":
            # 삭제
            answer[cur] = 'X'
            prev, next = table[cur]
            stack.append([prev, cur, next])
            if next == None:
                cur = table[cur][0]
            else:
                cur = table[cur][1]
            if prev == None:
                table[next][0] = None
            elif next == None:
                table[prev][1] = None
            else:
                table[prev][1] = next
                table[next][0] = prev

        elif c == "Z":
            # 복구
            prev, now, next = stack.pop()
            answer[now] = 'O'
            if prev == None:
                table[next][0] = now
            elif next == None:
                table[prev][1] = now
            else:
                table[next][0] = now
                table[prev][1] = now

        else:
            # 커서 이동
            c1, c2 = c.split(' ')
            c2 = int(c2)
            if c1 == 'D':
                for _ in range(c2):
                    cur = table[cur][1]
            else:
                for _ in range(c2):
                    cur = table[cur][0]
    return ''.join(answer)

 

📌리뷰

- linked list 설명

[Python 자료구조] 연결리스트(Linked List) feat.LeetCode