Coding 공부

import heapq
def solution(n, k, cmds):
    answer = ''
    def inverse(num):
        return -num
    max_heap = list(map(inverse,range(k)))
    min_heap = list(range(k,n))
    deleted = ['O' for _ in range(n)]
    deleted_stack = []
    heapq.heapify(max_heap)
    heapq.heapify(min_heap)
    for cmd in cmds:
        command = cmd.split()
        if len(command)>1:
            num = command[1]
            command = command[0]
            num = int(num)
            if command == 'D':
                for _ in range(num):
                    heapq.heappush(max_heap,-heapq.heappop(min_heap))
            else:
                for _ in range(num):
                    heapq.heappush(min_heap,-heapq.heappop(max_heap))
        else:
            command = command[0]
            if command == 'C':
                delete_num = heapq.heappop(min_heap)
                deleted_stack.append(delete_num)
                deleted[delete_num] = 'X'
                if len(min_heap) == 0:
                    heapq.heappush(min_heap,-heapq.heappop(max_heap))
            else:
                restore_num = deleted_stack.pop()
                deleted[restore_num] = 'O'
                if min_heap[0] > restore_num:
                    heapq.heappush(max_heap,-restore_num)
                else:
                    heapq.heappush(min_heap,restore_num)
    answer = ''.join(deleted)
    return answer

2021 카카오 채용연계형 인턴십에서 나왔던 3번 문제인 표 편집을 다시 풀어보았다.

그때는 효율성에서 통과 못했던 문제였던지라, 문제가 공개되자마자 푼 문제이다.

시험이 끝난 후 생각했던 풀이를 옮기는 작업으로 많이 걸리지 않았지만, 바보같이 python2로 제출을 해서 오래걸렸다.

첫 풀이는

https://www.acmicpc.net/problem/1655

백준의 가운데를 말해요 와

https://www.acmicpc.net/problem/21944

 문제 추천 시스템 version2에서 풀었던 풀이를 이용했다.

가운데를 말해요에서 처럼 가운데에 유지해야할 인수를 선택된 행으로 해주면 된다.

나는 그걸 min_heap의 최저값으로 유지를 해줬다.

max_heap과 min_heap 2개로 나뉜 상태에서 문제에서 주어진 k보다 크거나 같은 수는 min_heap에 그대로 넣어줘서, 저장을 해줬고, k보다 작은 수는 max_heap에 -를 곱해서 넣어줬다.

heap을 넣었다 뺐다하면, 시간이 오래걸리니 heapq의 heapify 메소드를 이용해 한번에 바꿔주었다.

이 상태에서 min_heap의 최저값이 우리가 선택한 인덱스가 유지해주게 되면 된다.

U 명령어와 같은경우엔 우리가 선택한 인덱스가 줄어들어야한다.

그래서 max_heap에서 인수를 꺼내서 -1을 곱한뒤 min_heap에 넣어준다.

그와 반대로 D 명령어는 우리가 선택한 인덱스가 늘어나야하므로,

min_heap에서 인수를 꺼내서 -1을 곱한뒤 max_heap에 넣어준다.

다음으로 지우는 명령어인 C가 주의해야한다.

먼저 C를 시행하는 방법은 우리가 봤던 index를 없애는 것이므로, min_heap에서 빼준뒤, 그 값을 스택에 넣어주고,

상태를 변화를 해준다.

이대로 그대로 하면 min_heap이 아무것도 안남는경우가 생길것이다. 즉 길이가 5인데 만약에 k가 4인 상태에서

C명령어를 수행하면 min_heap이 전부 비워지게 된다. 그러면 가리키는 인덱스가 없어지는 것이므로, 

max_heap에서 하나를 꺼내와서 min_heap에 넣어주는 작업을 해주면 된다.

Z 명령어는 간단하다.

우리가 삭제한 변수들을 저장한 스택에서 pop을 한뒤 그 인자가

현재 우리가 가리키는 인덱스 보다 작으면  max_heap에 넣어주고 크면 min_heap에 넣어주면 된다.

이렇게 한뒤 마지막으로 상태를 join을 한뒤 돌려주면 된다.

class Node():
    def __init__(self,data):
        self.prev = None
        self.next = None
        self.data = data
        

def solution(n,k,cmds):
    node_list = [Node(0)]
    deleted_stack = []
    deleted_state = ['O' for _ in range(n)]
    for num in range(1,n):
        prev_num = node_list[num-1]
        cur_num = Node(num)
        prev_num.next = cur_num
        cur_num.prev = prev_num
        node_list.append(cur_num)
    
    cur_node = node_list[k]

    for cmd in cmds:
        command = cmd.split()
        if len(command)>1:
            num = int(command[1])
            command = command[0]
            if command =='D':
                for _ in range(num):
                    cur_node = cur_node.next
            else:
                for _ in range(num):
                    cur_node = cur_node.prev
        else:
            command = command[0]
            if command == 'C':
                prev_num = cur_node.prev
                next_num = cur_node.next
                if next_num == None:
                    prev_num.next = None
                    deleted_stack.append(cur_node)
                    deleted_state[cur_node.data] = 'X'
                    cur_node = prev_num
                elif prev_num == None:
                    next_num.prev = None
                    deleted_stack.append(cur_node)
                    deleted_state[cur_node.data] = 'X'
                    cur_node = next_num
                else:
                    prev_num.next = next_num
                    next_num.prev = prev_num
                    deleted_stack.append(cur_node)
                    deleted_state[cur_node.data] = 'X'
                    cur_node = next_num
            else:
                restore_node = deleted_stack.pop()
                prev_num = restore_node.prev
                next_num = restore_node.next
                if prev_num != None:
                    prev_num.next = restore_node
                if next_num != None:
                    next_num.prev = restore_node
                deleted_state[restore_node.data] = 'O'
    answer = ''.join(deleted_state)
    return answer

두번째는 해설에도 나온 링크드리스트를 활용해서 풀면된다.

여기서 주의해야할 점은 prev나 next가 None일때 예외 처리르 어떻게 해주는지 이다. 그 외에는 일반적으로 하면 된다.

좀 더 개선한 코드는 

class Node():
    def __init__(self,data):
        self.prev = None
        self.next = None
        self.data = data
        

def solution(n,k,cmds):
    node_list = [Node(0)]
    deleted_stack = []
    deleted_state = ['O' for _ in range(n)]
    for num in range(1,n):
        prev_num = node_list[num-1]
        cur_num = Node(num)
        prev_num.next = cur_num
        cur_num.prev = prev_num
        node_list.append(cur_num)
    
    cur_node = node_list[k]

    for cmd in cmds:
        command = cmd.split()
        if len(command)>1:
            num = int(command[1])
            command = command[0]
            if command =='D':
                for _ in range(num):
                    cur_node = cur_node.next
            else:
                for _ in range(num):
                    cur_node = cur_node.prev
        else:
            command = command[0]
            if command == 'C':
                prev_num = cur_node.prev
                next_num = cur_node.next
                deleted_stack.append(cur_node)
                deleted_state[cur_node.data] = 'X'
                if next_num != None:
                    next_num.prev = prev_num
                if prev_num != None:
                    prev_num.next = next_num
                if next_num != None:
                    cur_node = next_num
                else:
                    cur_node = prev_num
            else:
                restore_node = deleted_stack.pop()
                prev_num = restore_node.prev
                next_num = restore_node.next
                if prev_num != None:
                    prev_num.next = restore_node
                if next_num != None:
                    next_num.prev = restore_node
                deleted_state[restore_node.data] = 'O'
    answer = ''.join(deleted_state)
    return answer

이 코드이다.

정확한 해설은 이보다 https://tech.kakao.com/2021/07/08/2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%9D%B8%ED%84%B4%EC%8B%AD-for-tech-developers-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%B4%EC%84%A4/

여기가 잘 설명되어있다.