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

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

프로그래머스

표를 주어진 연산에 따라 수정 하였을때 최종 적인 표의 모양을 출력하는 문제이다.

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

 

정확성과 효율성이 모두 필요한 문제이다. 문제를 보고 풀이를 떠올렸지만 역시 효율성 테스트에서 틀렸던 문제이다.

처음에는 리스트를 순회하며 커서를 이동하고, 삭제한뒤에도 리스트를 순회하면서 커서의 다음 위치를 구하는 방법으로 풀었다. 한번 연산을 수행하는데 최악의 경우 O(n)의 시간 복잡도를 가지는 풀이였다.

처음 틀렸던 코드는 다음과 같다.

 

def solution(n, k, cmd):
    stack = []
    chart = [True for _ in range(n)]
    for line in cmd:
        if line == "Z":
            chart[stack.pop()] = True
        elif line == "C":
            chart[k] = False
            stack.append(k)
            is_last = True
            for i in range(k + 1, n):
                if chart[i]:
                    is_last = False
                    k = i
                    break
            if is_last:
                while True:
                    k = k - 1
                    if chart[k]:
                        break
        else:
            commend, offset = line.split(" ")
            offset = int(offset)
            if commend == "U":
                while True:
                    k = k - 1
                    if chart[k]:
                        offset = offset - 1
                    if offset == 0:
                        break
            if commend == "D":
                while True:
                    k = k + 1
                    if chart[k]:
                        offset = offset - 1
                    if offset == 0:
                        break
    result = []
    for i in range(n):
        if chart[i]:
            result.append("O")
        else:
            result.append("X")
    return "".join(result)


print(solution(8, 2, ["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z"]))
print(solution(8, 2, ["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C"]))

시간복잡도를 개선하기 위해선 링크드리스트가 필요하다고 생각했다.

 

링크드 리스트란 하나의 노드에 값 노드간의 연결관계를 저장하는 자료구조이다,

이 문제에서는 노드에 이전노드의 값, 다음노드의 값, 삭제여부를 저장하였다. 특정한 노드를 찾는데는 오래걸리지만 현재위치를 알고있다면 다음노드를 찾는 연산, 노드의 삽입, 삭제에는 시간 복잡도가 낮은 특징이 있다.

 

하지만 링크드리스트를 사용하는 문제에 익숙하지 않아 구현시간이 오래걸렸다. 백준, 프로그래머스에서는 거의 처음보는 유형이 었다.

def solution(n, k, cmd):

    stack = []
    chart = [[x - 1, x + 1, True] for x in range(n)]
    chart[0][0] = -1
    chart[-1][1] = -1

    for line in cmd:
        if line == "Z":
            num, prev, next = stack.pop()
            chart[num][2] = True
            if prev == -1:
                chart[next][0] = num
            elif next == -1:
                chart[prev][1] = num
            else:
                chart[next][0] = num
                chart[prev][1] = num
        elif line == "C":
            chart[k][2] = False
            prev, next = chart[k][0], chart[k][1]
            stack.append([k, prev, next])
            # 커서 이동
            if next == -1:
                k = chart[k][0]
            else:
                k = chart[k][1]
            # 연결관계
            if prev == -1:
                chart[next][0] = -1
            elif next == -1:
                chart[prev][1] = -1
            else:
                chart[prev][1] = next
                chart[next][0] = prev
        else:
            commend, offset = line.split(" ")
            offset = int(offset)
            if commend == "U":
                for _ in range(offset):
                    k = chart[k][0]
            if commend == "D":
                for _ in range(offset):
                    k = chart[k][1]
    result = []
    for i in range(n):
        if chart[i][2]:
            result.append("O")
        else:
            result.append("X")
    return "".join(result)


print(solution(8, 2, ["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z"]))
print(solution(8, 2, ["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C"]))

클래스를 사용했다면 좀 더 가독성는 코드가 되지않았을까... 하는 생각

나중에 한번 더 풀어봐야할문제...