[2021 카카오 채용연계형 인턴쉽] 표 편집

⭐️ 표 편집

첫 제출에 8점을 받았습니다. ㅋㅋㅋㅋㅋㅋ 코드에서 문제가 뭐였고 개선할 점을 찾아서 나아가봅시다.

 

def solution(n, k, cmd):
    # print(n, k ,cmd ) #  n 행의수   k. 행의 위치 cmd 명령어
    answer = ''
    cursor = k
    true_table = [i for i in range(n)]
    table = [i for i in range(n)]
    deleted = []
    for i in range(len(cmd)):
        prefix = cmd[i][0]
        if prefix == 'U':
            cursor -= int(cmd[i][-1])
        if prefix == 'D':
            cursor += int(cmd[i][-1])
        if prefix == 'C':
            deleted_index = cursor
            # c 이면 딜리트후 바로아래선택 하짐나 마지막 삭제시 위칸 선택
            if len(table) - 1 == cursor:
                cursor -= 1

            new_table = table[0: deleted_index] + table[deleted_index + 1:]
            deleted.append((deleted_index, table[deleted_index]))
            # print(new_table)
            table = new_table
        if prefix == 'Z':
            index, who = deleted.pop()
            if index <= cursor:
                cursor += 1
            restore_table = table[0: index] + [who] + table[index : ]
            table = restore_table
        # print(table, cursor)
    #         print(table[0:index], who, table[index:] , 'check')
    #         print(restore_table, 'www')
    #     print(deleted)
    # print(restore_table)
    # print(true_table)
    i , j = 0 , 0 
    while j != len(true_table):

        if table[i] == true_table[j]:
            i = i+ 1
            j = j+ 1
            answer += 'O'
        else :
            j = j + 1
            answer += 'X'

    return answer

 

우선 restore_table이며 new_table 이며 변수가 너무 많다고 생각합니다. 이를 개선해보겠습니다.

두번째 풀이에는 변수를 줄이고 나름대로 최적화 했다고 생각을 했는데 6점맞았습니다. 런타임 에러가 왜뜰까요??

 

def solution(n, k, cmd):
    # n 행의 개수 , k 는 행의 위치, cmd는 명령어의 배열
    table = [i for i in range(n)]
    deleted = []
    cursor = k 
    for i in range(len(cmd)):
        command = cmd[i][0]
        if command == 'U':
            cursor -= int(cmd[i][-1])
        elif command == 'D':
            cursor += int(cmd[i][-1])
        elif command == 'C':
            deleted.append(table[cursor])
            del table[cursor]
            if cursor == len(table):
                cursor -= 1
        elif command == 'Z':
            _insert = deleted.pop()
            for i in range(len(table)):
                if table[i] > _insert:
                    table.insert(_insert, i)
                    if cursor >= i: 
                        cursor += 1
                    break
                if i == len(table) - 1:
                    table.append(_insert)
                    break

    i , j = 0 , 0
    answer = ''
    while j != n:
        if table[i] == j :
            i = i + 1
            j = j + 1
            answer += 'O'
        else:
            j = j + 1
            answer += 'X'

    print(answer)
    return answer

 

이제 코드를 좀 바꿔보겠습니다. cmd 개수는 20만개입니다. 따라서 이문제를 O(n^2) 으로 풀면 시간초과가 날 것으로 생각됩니다. 배열의 개수 또한 1,000,000 이므로 O(N)에 근사하게 풀어야 할 것을 알수있습니다. 결국 앞 노드와 뒷 노드가 연결된 연결리스트로 풀어야합니다.

 

def solution(n, k, cmds):
    answer = ''
    nodes = {0: [n-1,1]}
    for i in range(1, n):
        if i == n-1:
            nodes[i] = [i-1, 0]
        else:
            nodes[i] = [i-1, i+1]
    stack = []
    for cmd in cmds:
        if len(cmd) > 1:
            c, x = cmd.split(' ')
            cnt = 0
            if c == 'D':
                while cnt < int(x):
                    k = nodes[k][1]
                    cnt += 1
            else:
                while cnt < int(x):
                    k = nodes[k][0]
                    cnt += 1
        else:
            if cmd == 'C':
                nodes[nodes[k][0]][1] = nodes[k][1]
                nodes[nodes[k][1]][0] = nodes[k][0]
                stack.append([k, nodes[k]])
                tmp = nodes[k]
                del nodes[k]
                if tmp[1] == 0:
                    k = tmp[0]
                else:
                    k = tmp[1]
            else:
                curr_node, val = stack.pop()
                prev_node, next_node = val
                nodes[curr_node] = [prev_node, next_node]
                nodes[prev_node][1] = curr_node
                nodes[next_node][0] = curr_node
    result = ''
    for i in range(n):
        if nodes.get(i) is None:
            result += 'X'
        else:
            result += 'O'


    return result

✅ JavaScript 풀이

class Node {
    constructor(value, prev, next) {
        this.value = value;
        this.prev = prev;
        this.next = next;
    }
};

function solution(n, k, cmd) {
    const table = Array.from({length:n}, () => true);
    const nodes = Array.from({length:n}, () => new Node());
    const removed = [];
    let cur = nodes[k];

    for(let i = 0; i < n; i++) {
        nodes[i].value = i;
        nodes[i].prev = nodes[i - 1];
        nodes[i].next = nodes[i + 1];
    }

    cmd.forEach(command => {
        command = command.split(" ");
        switch(command[0]) {
            case "U":
                for(let i = 0; i < command[1]; i++) {
                    cur = cur.prev;
                }
                break;
            case "D":
                for(let i = 0; i < command[1]; i++) {
                    cur = cur.next;
                }
                break;
            case "C":
                table[cur.value] = false;
                removed.push(cur);
                if(cur.next === undefined) {
                    cur = cur.prev;
                    cur.next = undefined;
                } else if(cur.prev === undefined) {
                    cur.next.prev = undefined;
                    cur = cur.next;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    cur = cur.next;
                }
                break;
            case "Z":
                const restored = removed.pop();
                table[restored.value] = true;
                if(restored.prev !== undefined)
                    restored.prev.next = restored;
                if(restored.next !== undefined)
                    restored.next.prev = restored;
                break;
        }
    })

    return table.map(row => row ? "O" : "X").join("");
}