[프로그래머스][KAKAO_인턴][2021] 표 편집

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

코딩테스트 연습 - 표 편집

 

내가 작성한 코드

class node:
    def __init__(self, x=-1, l=None, r=None):
        self.x = x
        self.l = l
        self.r = r

def pop(l, r):
    if l:
        l.r = r
    if r:
        r.l = l
    return r or l

def insert(n, l ,r):
    if l:
        l.r, n.l = n, l
    if r:
        r.l, n.r = n, r

def solution(n, k, cmd):
    answer = []
    stk = []
    head = node()
    now = None
    crnt = head
    for i in range(n):
        nw_node = node(i, crnt)
        crnt.r, crnt = nw_node, nw_node
        if i == k:
            now = crnt

    for c in cmd:
        if c[0] == "U":
            for _ in range(int(c.split()[1])):
                now = now.l
        elif c[0] == "D":
            for _ in range(int(c.split()[1])):
                now = now.r
        elif c[0] == "C":
            stk.append((now, now.l, now.r))
            now = pop(now.l, now.r)
        elif c[0] == "Z":
            insert(*stk.pop())

    crnt = head
    for i in range(n):
        if crnt.r and crnt.r.x == i:
            answer.append('O')
            crnt = crnt.r
        else:
            answer.append('X')

    return ''.join(answer)

• 연결리스트
  
  • 각 인덱스 값을 가진 연결리스트로 명령 수행
  • 수행이 끝나고 전체 탐색하여 인덱스와 일치하는 값이 위치에 없는 경우 X 삽입

 

다른 사람이 작성한 코드

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

    linked_list = {i: [i - 1, i + 1] for i in range(1, n+1)} #n=8일때 1~8까지
    OX = ["O" for i in range(1,n+1)]
    stack = []

    k += 1

    for c in cmd:
        if c[0] == 'D':
            for _ in range(int(c[2:])):
                k = linked_list[k][1]
        elif c[0] == 'U':
            for _ in range(int(c[2:])):
                k = linked_list[k][0]
        elif c[0] == 'C':
            prev, next = linked_list[k]
            stack.append([prev, next, k])
            OX[k-1] = "X"

            if next == n+1:
                k = linked_list[k][0]
            else:
                k = linked_list[k][1]

            if prev == 0:
                linked_list[next][0] = prev
            elif next == n+1:
                linked_list[prev][1] = next
            else:
                linked_list[prev][1] = next
                linked_list[next][0] = prev

        elif c[0] == 'Z':
            prev, next, now = stack.pop()
            OX[now-1] = "O"

            if prev == 0:
                linked_list[next][0] = now
            elif next == n+1:
                linked_list[prev][1] = now
            else:
                linked_list[prev][1] = now
                linked_list[next][0] = now

    return "".join(OX)

• 연결리스트 문제라는 것을 이 분의 설명을 통해 깨달았다

 

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

[파이썬 python] 프로그래머스 - 표 편집

 

기억해야할 것

• 연결리스트의 힌트
  
  • 인덱스를 사용하지 않고 위/아래로 움직임
  • 배열의 중간 요소에 대한 제거/삽입이 빈번함