-
2021 카카오 채용연계형 인턴십: 표 편집코딩 테스트/Level 3 2021. 9. 24. 18:41반응형
https://programmers.co.kr/learn/courses/30/lessons/81303
코딩테스트 연습 - 표 편집
8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO"
programmers.co.kr
파이썬
문제를 제대로 이해했는 지 확인...
def solution(n, k, cmd): temp = [i for i in range(n)] undos = [] for command in cmd: if command[0] == 'U': k -= int(command[2:]) elif command[0] == 'D': k += int(command[2:]) elif command[0] == 'C': undos.append((k, temp[k])) temp.pop(k) if len(temp) <= k: k -= 1 elif command[0] == 'Z': pos, undo = undos.pop() temp.insert(pos, undo) if pos <= k: k += 1 return ''.join(['O' if each in temp else 'X' for each in range(n)])리스트에서 pop을 할 때
마지막 원소가 아니라면
속도가 무척 느리다는 건 상식...
당연히 효율성에서 떨어짐...정확성 테스트 테스트 1 〉 통과 (0.03ms, 10.3MB) 테스트 2 〉 통과 (0.03ms, 10.5MB) 테스트 3 〉 통과 (0.03ms, 10.4MB) 테스트 4 〉 통과 (0.05ms, 10.5MB) 테스트 5 〉 통과 (0.10ms, 10.4MB) 테스트 6 〉 통과 (0.10ms, 10.4MB) 테스트 7 〉 통과 (0.16ms, 10.4MB) 테스트 8 〉 통과 (0.10ms, 10.4MB) 테스트 9 〉 통과 (0.10ms, 10.4MB) 테스트 10 〉 통과 (0.10ms, 10.4MB) 테스트 11 〉 통과 (1.50ms, 10.5MB) 테스트 12 〉 통과 (1.70ms, 10.4MB) 테스트 13 〉 통과 (1.51ms, 10.4MB) 테스트 14 〉 통과 (1.49ms, 10.5MB) 테스트 15 〉 통과 (1.41ms, 10.4MB) 테스트 16 〉 통과 (1.41ms, 10.4MB) 테스트 17 〉 통과 (5.50ms, 10.5MB) 테스트 18 〉 통과 (5.49ms, 10.5MB) 테스트 19 〉 통과 (5.24ms, 10.4MB) 테스트 20 〉 통과 (5.32ms, 10.4MB) 테스트 21 〉 통과 (5.31ms, 10.4MB) 테스트 22 〉 통과 (5.57ms, 10.4MB) 테스트 23 〉 통과 (0.04ms, 10.4MB) 테스트 24 〉 통과 (0.03ms, 10.5MB) 테스트 25 〉 통과 (0.03ms, 10.4MB) 테스트 26 〉 통과 (0.02ms, 10.4MB) 테스트 27 〉 통과 (0.04ms, 10.5MB) 테스트 28 〉 통과 (0.04ms, 10.4MB) 테스트 29 〉 통과 (0.05ms, 10.4MB) 테스트 30 〉 통과 (0.05ms, 10.4MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과) 테스트 6 〉 실패 (시간 초과) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (시간 초과) 테스트 9 〉 실패 (시간 초과) 테스트 10 〉 실패 (시간 초과)문제는 제대로 이해한 것 같고...
딕셔너리로 더블(양방향) 링크드(연결) 리스트를 구현해 풀어봄.4. 양방향 연결 리스트 (Doubly linked list ADT) 파이썬
단방향 연결리스트는 역방향 탐색이 쉽지 않습니다. 이를 해결하는 가장 쉬운 방법은 이전 노드의 링크를 만들어 주는 것입니다. 이럴 경우 메모리를 좀 더 소모하고, 프로그램이 약간 복잡해지
comdoc.tistory.com
def solution(n, k, commands): result = ['O' for _ in range(n)] links = {i: [i - 1, i + 1] for i in range(n)} undos = [] for command in commands: if command[0] == 'D': for _ in range(int(command[2:])): k = links[k][1] elif command[0] == 'U': for _ in range(int(command[2:])): k = links[k][0] elif command[0] == 'C': p_node, n_node = links[k] undos.append((k, p_node, n_node)) result[k] = 'X' k = links[k][0] if n_node == n else links[k][1] if p_node != -1: links[p_node][1] = n_node if n_node != n: links[n_node][0] = p_node elif command[0] == 'Z': c_node, p_node, n_node = undos.pop() result[c_node] = 'O' if p_node != -1: links[p_node][1] = c_node if n_node != n: links[n_node][0] = c_node return ''.join(result)정확성 테스트 테스트 1 〉 통과 (0.03ms, 10.4MB) 테스트 2 〉 통과 (0.03ms, 10.5MB) 테스트 3 〉 통과 (0.03ms, 10.4MB) 테스트 4 〉 통과 (0.03ms, 10.4MB) 테스트 5 〉 통과 (0.09ms, 10.5MB) 테스트 6 〉 통과 (0.09ms, 10.5MB) 테스트 7 〉 통과 (0.08ms, 10.4MB) 테스트 8 〉 통과 (0.08ms, 10.5MB) 테스트 9 〉 통과 (0.08ms, 10.4MB) 테스트 10 〉 통과 (0.08ms, 10.3MB) 테스트 11 〉 통과 (0.48ms, 10.6MB) 테스트 12 〉 통과 (0.51ms, 10.5MB) 테스트 13 〉 통과 (0.48ms, 10.4MB) 테스트 14 〉 통과 (0.97ms, 10.5MB) 테스트 15 〉 통과 (1.01ms, 10.5MB) 테스트 16 〉 통과 (1.09ms, 10.3MB) 테스트 17 〉 통과 (4.34ms, 10.5MB) 테스트 18 〉 통과 (4.36ms, 10.6MB) 테스트 19 〉 통과 (4.04ms, 10.5MB) 테스트 20 〉 통과 (2.17ms, 10.6MB) 테스트 21 〉 통과 (2.00ms, 10.6MB) 테스트 22 〉 통과 (2.17ms, 10.7MB) 테스트 23 〉 통과 (0.03ms, 10.5MB) 테스트 24 〉 통과 (0.04ms, 10.3MB) 테스트 25 〉 통과 (0.02ms, 10.5MB) 테스트 26 〉 통과 (0.02ms, 10.5MB) 테스트 27 〉 통과 (0.04ms, 10.5MB) 테스트 28 〉 통과 (0.04ms, 10.4MB) 테스트 29 〉 통과 (0.04ms, 10.5MB) 테스트 30 〉 통과 (0.06ms, 10.4MB) 효율성 테스트 테스트 1 〉 통과 (833.37ms, 234MB) 테스트 2 〉 통과 (878.61ms, 234MB) 테스트 3 〉 통과 (844.26ms, 234MB) 테스트 4 〉 통과 (894.26ms, 242MB) 테스트 5 〉 통과 (890.57ms, 242MB) 테스트 6 〉 통과 (818.83ms, 244MB) 테스트 7 〉 통과 (208.70ms, 68.5MB) 테스트 8 〉 통과 (256.72ms, 77.6MB) 테스트 9 〉 통과 (796.16ms, 245MB) 테스트 10 〉 통과 (810.11ms, 245MB)이 방법으론 시간 제한을 통과할 수 없었다.
def solution(n, k, commands): length = n undos = [] for command in commands: if command[0] == 'U': k -= int(command[2:]) elif command[0] == 'D': k += int(command[2:]) elif command[0] == 'C': undos.append(k) length -= 1 if length == k: k -= 1 elif command[0] == 'Z': pos = undos.pop() length += 1 if pos <= k: k += 1 answer = ['O' for _ in range(length)] for each in undos[::-1]: answer.insert(each, 'X') return ''.join(answer)정확성 테스트 테스트 1 〉 통과 (0.02ms, 10.5MB) 테스트 2 〉 통과 (0.03ms, 10.3MB) 테스트 3 〉 통과 (0.03ms, 10.3MB) 테스트 4 〉 통과 (0.02ms, 10.2MB) 테스트 5 〉 통과 (0.04ms, 10.3MB) 테스트 6 〉 통과 (0.07ms, 10.3MB) 테스트 7 〉 통과 (0.07ms, 10.3MB) 테스트 8 〉 통과 (0.05ms, 10.4MB) 테스트 9 〉 통과 (0.04ms, 10.3MB) 테스트 10 〉 통과 (0.06ms, 10.3MB) 테스트 11 〉 통과 (0.26ms, 10.3MB) 테스트 12 〉 통과 (0.14ms, 10.3MB) 테스트 13 〉 통과 (0.15ms, 10.4MB) 테스트 14 〉 통과 (0.15ms, 10.3MB) 테스트 15 〉 통과 (0.23ms, 10.4MB) 테스트 16 〉 통과 (0.14ms, 10.3MB) 테스트 17 〉 통과 (0.27ms, 10.4MB) 테스트 18 〉 통과 (0.48ms, 10.3MB) 테스트 19 〉 통과 (0.54ms, 10.4MB) 테스트 20 〉 통과 (0.46ms, 10.4MB) 테스트 21 〉 통과 (0.30ms, 10.4MB) 테스트 22 〉 통과 (0.50ms, 10.2MB) 테스트 23 〉 통과 (0.02ms, 10.3MB) 테스트 24 〉 통과 (0.66ms, 10.5MB) 테스트 25 〉 통과 (0.02ms, 10.2MB) 테스트 26 〉 통과 (0.03ms, 10.4MB) 테스트 27 〉 통과 (0.03ms, 10.4MB) 테스트 28 〉 통과 (0.03ms, 10.2MB) 테스트 29 〉 통과 (0.03ms, 10.3MB) 테스트 30 〉 통과 (0.04ms, 10.5MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 통과 (4203.91ms, 22.8MB) 테스트 3 〉 통과 (1831.25ms, 21.9MB) 테스트 4 〉 통과 (72.93ms, 28.2MB) 테스트 5 〉 통과 (80.57ms, 28.4MB) 테스트 6 〉 실패 (시간 초과) 테스트 7 〉 통과 (1750.00ms, 19.5MB) 테스트 8 〉 통과 (4146.97ms, 23.9MB) 테스트 9 〉 실패 (시간 초과) 테스트 10 〉 실패 (시간 초과)heap을 이용한 풀이도 재미있다.
최대힙 최소힙을 만들어서 주거니 받거니 하면서 물제를 풀어나간다..
의외로 빠르다~!https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88
파이썬의 heapq 모듈
https://docs.python.org/ko/3.7/library/heapq.html 힙큐는 최솟값(또는 최댓값)을 계속 뽑아내야 할 때 사용할 수 있습니다. 한 번 정렬해 놓고 하나씩 뽑으면 되지 않냐? 맞습니다. 하지만 계속 새로운 값들
comdoc.tistory.com
from heapq import heapify, heappush, heappop def solution(n, k, commands): max_heap = [-i for i in range(k)] min_heap = [i for i in range(k, n)] result = ['O' for _ in range(n)] undos = [] heapify(max_heap) heapify(min_heap) for command in commands: if command[0] == 'D': for _ in range(int(command[2:])): heappush(max_heap, -heappop(min_heap)) elif command[0] == 'U': for _ in range(int(command[2:])): heappush(min_heap, -heappop(max_heap)) elif command[0] == 'C': num = heappop(min_heap) undos.append(num) result[num] = 'X' if len(min_heap) == 0: heappush(min_heap, -heappop(max_heap)) else: undo = undos.pop() result[undo] = 'O' if min_heap[0] > undo: heappush(max_heap, -undo) else: heappush(min_heap, undo) return ''.join(result)정확성 테스트 테스트 1 〉 통과 (0.04ms, 10.4MB) 테스트 2 〉 통과 (0.03ms, 10.4MB) 테스트 3 〉 통과 (0.03ms, 10.4MB) 테스트 4 〉 통과 (0.04ms, 10.5MB) 테스트 5 〉 통과 (0.16ms, 10.4MB) 테스트 6 〉 통과 (0.18ms, 10.5MB) 테스트 7 〉 통과 (0.20ms, 10.4MB) 테스트 8 〉 통과 (0.18ms, 10.5MB) 테스트 9 〉 통과 (0.17ms, 10.5MB) 테스트 10 〉 통과 (0.13ms, 10.5MB) 테스트 11 〉 통과 (2.45ms, 10.4MB) 테스트 12 〉 통과 (1.59ms, 10.5MB) 테스트 13 〉 통과 (2.40ms, 10.4MB) 테스트 14 〉 통과 (4.74ms, 10.4MB) 테스트 15 〉 통과 (5.46ms, 10.4MB) 테스트 16 〉 통과 (5.47ms, 10.4MB) 테스트 17 〉 통과 (23.70ms, 10.5MB) 테스트 18 〉 통과 (24.22ms, 10.4MB) 테스트 19 〉 통과 (31.94ms, 10.4MB) 테스트 20 〉 통과 (11.73ms, 10.6MB) 테스트 21 〉 통과 (18.82ms, 10.4MB) 테스트 22 〉 통과 (9.17ms, 10.5MB) 테스트 23 〉 통과 (0.03ms, 10.5MB) 테스트 24 〉 통과 (0.04ms, 10.5MB) 테스트 25 〉 통과 (0.03ms, 10.4MB) 테스트 26 〉 통과 (0.04ms, 10.4MB) 테스트 27 〉 통과 (0.04ms, 10.4MB) 테스트 28 〉 통과 (0.06ms, 10.5MB) 테스트 29 〉 통과 (0.05ms, 10.5MB) 테스트 30 〉 통과 (0.04ms, 10.4MB) 효율성 테스트 테스트 1 〉 통과 (769.62ms, 62.2MB) 테스트 2 〉 통과 (686.72ms, 62.7MB) 테스트 3 〉 통과 (809.94ms, 62MB) 테스트 4 〉 통과 (484.06ms, 68.3MB) 테스트 5 〉 통과 (478.66ms, 68.2MB) 테스트 6 〉 통과 (278.05ms, 66.2MB) 테스트 7 〉 통과 (182.98ms, 26.6MB) 테스트 8 〉 통과 (230.36ms, 31.5MB) 테스트 9 〉 통과 (289.13ms, 66.7MB) 테스트 10 〉 통과 (259.53ms, 66.7MB)반응형