[PRO] 표 편집

천호영·2022년 5월 2일
0

알고리즘

목록 보기
14/100
post-thumbnail

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

초반에 제출한 코드는 다음과 같다. 존재하지 않으면 boolean값을 False로 두어 건너뛰도록 했다.
이때, 정확성 테스트는 모두 통과했으나 효율성 테스트는 절반만 통과했다.

def solution(n, k, cmd):
    bool_table = [True for _ in range(n)]
    selected_idx = k
    exist_max_idx = n-1
    deleted_idx_list = []
    
    
    for one_cmd in cmd:
        splited_cmd = one_cmd.split()
        
        if splited_cmd[0]=="Z":
            deleted_idx = deleted_idx_list.pop()
            bool_table[deleted_idx] = True
            exist_max_idx = max(exist_max_idx,deleted_idx)
            
        elif splited_cmd[0]=="C":
            deleted_idx_list.append(selected_idx)
            bool_table[selected_idx] = False
            if selected_idx == exist_max_idx:
                while not bool_table[selected_idx]: # 다음이 False일 수 있다!
                    selected_idx -= 1
                exist_max_idx = selected_idx
            else:
                while not bool_table[selected_idx]: # 다음이 False일 수 있다!
                    selected_idx += 1
        
        elif splited_cmd[0]=="U":
            distance = int(splited_cmd[1])
            while distance != 0:
                selected_idx -= 1
                if bool_table[selected_idx]:
                    distance -= 1
        
        elif splited_cmd[0]=="D":
            distance = int(splited_cmd[1])
            while distance != 0:
                selected_idx += 1
                if bool_table[selected_idx]:
                    distance -= 1

    return "".join(["O" if x else "X" for x in bool_table])

위 코드는 Z의 경우 O(1)이지만 C,U,D의 경우 O(N)이다. 따라서 양방향 연결리스트를 통해 시간복잡도를 낮춰야 한다.

아래 코드에서 C, Z는 O(1), U,D는 O(X)로 만들었다. X: 남아있는 행수
(출처)

def solution(n, k, cmd):
    cur = k # 현재 index
    answer = ['O'] * n # 정답인 존재하는지 여부
    
    table = { i:[i - 1, i + 1] for i in range(n) }
    table[0] = [None, 1]
    table[n - 1] = [n - 2, None]
    
    stack = [] #삭제한 행 정보 넣어두는 stack (prev,cur,next)형태로
    
    for c in cmd:
        if c == "C":
            # 삭제
            answer[cur] = 'X'
            prev, next = table[cur]
            stack.append([prev, cur, next])
            
            if next == None:
                cur = table[cur][0]
            else:
                cur = table[cur][1]
                
            if prev == None:
                table[next][0] = None
            elif next == None:
                table[prev][1] = None
            else:
                table[prev][1] = next
                table[next][0] = prev
        elif c == "Z":
            # 복구
            answer[now] = 'O'
            
            prev, now, next = stack.pop()
            if prev == None:
                table[next][0] = now
            elif next == None:
                table[prev][1] = now
            else:
                table[next][0] = now
                table[prev][1] = now
        else:
            # 커서 이동
            c1, c2 = c.split(' ')
            c2 = int(c2)
            if c1 == 'D':
                for _ in range(c2):
                    cur = table[cur][1]
            else:
                for _ in range(c2):
                    cur = table[cur][0]
    return ''.join(answer)
profile
성장!

0개의 댓글