★프로그래머스 2021 카카오 채용연계형 인턴십 표 편집

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

코딩테스트 연습 - 표 편집

 

처음 풀이 방법

단순하게 구현으로 풀이하였다. 역시 시간 초과.....

def solution(n, k, cmd):
    answer = ""
    deleted = [False] * (n)
    delete = []
    move = 0

    for cstr in cmd:
        if len(cstr) > 1:
            command, index = cstr.split()
            
            index = int(index)

            if command == "D":
                move += index
            elif command == "U":
                move -= index
        else:
            command = cstr
            if move<0:
                index = -move
                plus = [i for i in range(k-1,-1,-1) if deleted[i] == False]
                k = plus[index-1]

            elif move > 0:
                index = move
                plus = [i for i in range(k+1,n) if deleted[i] == False]
                k = plus[index-1]
            
            move = 0
            
            if command == "C":
                delete.append(k)
                deleted[k] = True
                plus = [i for i in range(k+1,n) if deleted[i] == False]
                if len(plus) == 0:
                    minus = [i for i in range(k-1,-1,-1) if deleted[i] == False]
                    k = minus[0]
                else:
                    k = plus[0]
                
            elif command == "Z":
                brings_back = delete.pop()
                deleted[brings_back] = False

                
    for i in deleted:
        if i == True:
            answer += "X"
        else:
            answer += "O"
    return answer

또 다른 아이디어

노드를 만들어서 링크드리스트를 구현해야 한다는 생각이 들었다.

하지만 실제로 시간 제한이 있는 코딩테스트 환경에서 이 방법을 사용하기는 힘들 것 같아서, 좀 더 실용적인 아이디어가 있지 않을까? 라는 생각에 다른 방법을 찾아보았다.

 

최종 방법

https://velog.io/@kerri/Swift-Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv3-%ED%91%9C-%ED%8E%B8%EC%A7%91-2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%B1%84%EC%9A%A9%EC%97%B0%EA%B3%84%ED%98%95-%EC%9D%B8%ED%84%B4%EC%8B%AD

[Swift / Python] 프로그래머스(Lv3) - 표 편집 (2021 카카오 채용연계형 인턴십)

풀이는 위의 링크를 참고하자.

링크드리스트 없이 배열로도 충분히 시간제한 통과가 가능하다.

 

def solution(n, k, cmd):
    answer = ''
    available = [True] * n
    up = [i for i in range(-1,n-1,1)]
    up[0] = 0
    down = [i for i in range(1,n+1,1)]
    down[-1] = n-1
    delete = []
    
    move = 0
    
    for cm in cmd:
        if len(cm)>1:
            command, index = cm.split()
            index = int(index)
            
            if command == "U":
                move -= index
            else:
                move += index
        else:
            if move>0:
                while move>0:
                    move -= 1
                    k = down[k]
            elif move<0:
                while move<0:
                    move += 1
                    k = up[k]
            
            if cm == "C":
                delete.append(k)
                available[k] = False
                down[up[k]] = down[k]
                if k != down[k]:
                    k = down[k]
                    up[k] = up[up[k]]
                else:
                    k = up[k]
                    down[k] = k
            else:
                back = delete.pop()
                available[back] = True
                if up[back] != back:
                    down[up[back]] = back
                if down[back] != back:
                    up[down[back]] = back
                
    for i in available:
        if i == True:
            answer += "O"
        else:
            answer += "X"
    return answer