카카오 기출 - 표편집

실패

from functools import reduce

def moveCur(movement, arr, curIdx, m):
    while movement > 0:
        curIdx += m
        if arr[curIdx][1] == 'O':
            movement -= 1
    return curIdx

def findNextIdx(curIdx, arr):
    length = len(arr)
    ret = curIdx

    while curIdx < length - 1:
        curIdx += 1
        if arr[curIdx][1] == 'O':
            return curIdx

    while ret > 0:
        ret -= 1
        if arr[ret][1] == 'O':
            return ret

def solution(n, k, cmd):
    answer = ''
    curIdx = k
    arr = [[_, 'O'] for _ in range(n)]
    deleteStack = []
    for command in cmd:
        if command.startswith("D"):
            move = int(command.split()[1])
            curIdx = moveCur(move, arr, curIdx, 1)
        elif command.startswith("U"):
            move = int(command.split()[1])
            curIdx = moveCur(move, arr, curIdx, -1)
        elif command == "C":
            arr[curIdx][1] = 'X'
            deleteStack.append(curIdx)
            curIdx = findNextIdx(curIdx, arr)
        elif command == "Z":
            redo = deleteStack.pop()
            arr[redo][1] = 'O'

    answer = reduce(lambda acc, cur: acc + cur[1], arr, answer)
    return answer

아마 대부분이 이렇게 풀었을거라 생각된다. 하지만 움직일때마다 배열의 모든 칸을 일일이 돌아야하므로 정확성은 모두 통과하더라도 효율성에서는 박살나는 코드다. 그래서 이전 인덱스와 다음 인덱스를 가리키는 것을 추가해봤다. 

이전 인덱스와 다음 인덱스를 저장하는 이차원 배열이다.

실패

from functools import reduce

def solution(n, k, cmd):
    answer = ''
    curIdx = k
    arr = [[_, 'O', _-1, _+1] for _ in range(n)]

    deleteStack = []
    for command in cmd:
        if command.startswith("D"):
            for i in range(int(command.split()[1])):
                curIdx = arr[curIdx][3]
        elif command.startswith("U"):
            for i in range(int(command.split()[1])):
                curIdx = arr[curIdx][2]

        elif command == "C":
            arr[curIdx][1] = 'X'
            deleteStack.append(curIdx)
            prevIdx = arr[curIdx][2]
            nextIdx = arr[curIdx][3]
            if prevIdx != -1 :
                arr[prevIdx][3] = nextIdx
            if nextIdx != n:
                arr[nextIdx][2] = prevIdx
            curIdx = nextIdx if nextIdx != n else prevIdx
            
        elif command == "Z":
            redo = deleteStack.pop()
            arr[redo][1] = 'O'
            prevIdx = arr[redo][2]
            nextIdx = arr[redo][3]
            if prevIdx != -1 :
                arr[prevIdx][3] = redo
            if nextIdx != n:
                arr[nextIdx][2] = redo

    answer = reduce(lambda acc, cur: acc + cur[1], arr, answer)
    return answer

효율성 두개를 통과하게 됐지만 이 코드도 마찬가지로 시간초과였다.. 배열말고 딕셔너리를 사용했다.

 

성공

def solution(n, k, cmd):
    answer = ''
    curIdx = k
    arr = { i: ['O', i-1, i+1] for i in range(n)}

    deleteStack = []
    for command in cmd:
        if command.startswith("D"):
            for i in range(int(command[2:])):
                curIdx = arr[curIdx][2]
        elif command.startswith("U"):
            for i in range(int(command[2:])):
                curIdx = arr[curIdx][1]

        elif command == "C":
            arr[curIdx][0] = 'X'
            deleteStack.append(curIdx)
            prevIdx = arr[curIdx][1]
            nextIdx = arr[curIdx][2]
            if prevIdx != -1 :
                arr[prevIdx][2] = nextIdx
            if nextIdx != n:
                arr[nextIdx][1] = prevIdx
            curIdx = nextIdx if nextIdx != n else prevIdx

        elif command == "Z":
            redo = deleteStack.pop()
            arr[redo][0] = 'O'
            prevIdx = arr[redo][1]
            nextIdx = arr[redo][2]
            if prevIdx != -1 :
                arr[prevIdx][2] = redo
            if nextIdx != n:
                arr[nextIdx][1] = redo


    for i in range(n) :
        answer += arr[i][0]
    return answer

 

 

참고자료

https://all-knowledge-of-the-world.tistory.com/17

[Python] Dictionary를 이용해 데이터를 빠르게 검색하고 타이머로 시간을 측정해 보자!

https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리