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
1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
백준의 가운데를 말해요 와
https://www.acmicpc.net/problem/21944
21944번: 문제 추천 시스템 Version 2
recommend, recommend2, recommend3 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 주어지는 recommend, recommend2, recommend3 명령어의 총 개수는 최소 1개 이상이다.
www.acmicpc.net
문제 추천 시스템 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
이 코드이다.
2021 카카오 인턴십 for Tech developers 코딩 테스트 해설
2021년 카카오의 여름 인턴십의 첫 번째 관문인 코딩 테스트가 지난 2021년 5월 8일에 4시간에 걸쳐 진행되었습니다. 이번 인턴 코딩 테스트에서는 5문제가 출제되었습니다. 이전과 동일하게 쉬운
tech.kakao.com
여기가 잘 설명되어있다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 81305 시험장 나누기 카카오 채용연계형 인턴십 (0) | 2021.07.11 |
|---|---|
| [프로그래머스] 81304 미로 탈출 2021 카카오 채용연계형 인턴십 (0) | 2021.07.11 |
| [프로그래머스] 42641 체육복 (0) | 2021.03.14 |
| [프로그래머스] 42840 모의고사 (0) | 2021.03.14 |
| [프로그래머스] 42576 완주하지 못한 선수 (0) | 2021.03.14 |