표 편집 (81303번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 표 편집 (81303번)

 

난이도 : Lv 3

알고리즘&자료구조 : Linked List (연결 리스트)

 

 

def solution(n, k, cmds):
    ll = [[i-1, i+1] for i in range(n)]
    stack = []
    
    for cmd in cmds:
        if cmd[0] == 'U':
            for _ in range(int(cmd[2:])):
                k = ll[k][0]
        elif cmd[0] == 'D':
            for _ in range(int(cmd[2:])):
                k = ll[k][1]
        elif cmd == 'C':
            stack.append(k)
            if ll[k][0] != -1:
                ll[ll[k][0]][1] = ll[k][1]
            if ll[k][1] != n:
                ll[ll[k][1]][0] = ll[k][0]
            k = ll[k][0] if ll[k][1] == n else ll[k][1]
        else:
            c = stack.pop()
            if ll[c][0] != -1:
                ll[ll[c][0]][1] = c
            if ll[c][1] != n:
                ll[ll[c][1]][0] = c
    
    while ll[k][0] != -1:
        k = ll[k][0]
    linked = [False] * n
    while k != n:
        linked[k] = True
        k = ll[k][1]
    return ''.join('O' if linked[i] else 'X' for i in range(n))

 

 

2021 카카오 채용연계형 인턴십 기출문제이다.

Linked List (연결 리스트) 를 활용해서 풀 수 있었다.

 

 

---

 

▷ 먼저 Linked List 로 활용할 "ll" 리스트를 만든다.

▷ 제거하는 행을 저장할 "stack" 리스트를 만든다.

 

 

 

① "U X" 일 때는, 현재 위치 k 에서 왼쪽으로 연결된 ll[k][0] 으로 X 번 이동한다.

 

 

② "D X" 일 때는, 현재 위치 k 에서 오른쪽으로 연결된 ll[k][1] 로 X 번 이동한다.

 

 

③ "C" 일 때는,

 

현재 위치의 왼쪽에 연결된 left = ll[k][0] 에서, left 오른쪽을 k 의 오른쪽에 연결된 right = ll[k][1] 과 연결한다.

ll[left][1] = ll[k][1]

 

현재 위치의 오른쪽에 연결된 right = ll[k][1] 에서, right 의 왼쪽을 k 의 왼쪽에 연결된  left = ll[k][0] 와 연결한다.

ll[right][0] = ll[k][0]

 

여기서 주의할 점은, 양 끝인 0 과 n-1 에서 예외처리를 잘 해줘야 한다.

 

 

④ "Z" 일 때는,

가장 최근에 삭제한 행을 stack 에서 꺼내와서,

삭제 전에 연결돼있던 왼쪽 left = ll[k][0] 과 오른쪽 right = ll[k][1] 을 다시 연결한다.

 

 

 

▷ 마지막으로, 현재 Liked List의 Head 로 돌아가서,

Tail 까지 내려가면서 "O" 와 "X" 를 판별하고 반환한다.