네발로 코딩하는 포메라니안

1. 문제 2. 풀이 과정 def find_p(p, n): while p[n] != n: #부모값이 자기 자신이면 root n = p[n] return n def solution(n, costs): answer = 0 parent = [i for i in range(n)] #부모를 자기 자신으로 초기화 c = sorted(costs, key = lambda x: x[2]) for i in range(len(c)): p1 = find_p(parent, c[i][0]) p2 = find_p(parent, c[i][1]) if p1 != p2: parent[p2] = p1 answer += c[i][2] return answer

1. 문제 2. 풀이 과정 방법 1) remove하면 heap구조가 깨지지만 잘 작동한다. 이유는 최댓값을 빼서 구조가 깨진 후, min_h에서 pop하거나 push할 때 다시 heap 구조를 만들기 때문이다. 따라서, 작동하는 데에는 문제가 없지만 max값을 찾는 데에서 시간이 비교적 많이 걸린다. import heapq as hq def solution(operations): answer = [0, 0] min_h = [] #기본 for operation in operations: order, num = operation.split() num = int(num) if order == 'I': hq.heappush(min_h, num) elif min_h and order == 'D': if num =..

1. 문제 2. 풀이 과정 방법 1) import heapq as hq def solution(jobs): answer = 0 jobs.sort() heap = [] count = 0 #시간 pre_idx = -1 while True: #전에 heap에 안들어갔었고, 현재 count보다 작은 값 heap에 넣기 temp = pre_idx for i in range(temp+1, len(jobs)): if jobs[i][0] > count: break hq.heappush(heap, [jobs[i][1], jobs[i][0]]) pre_idx = i if heap: e = hq.heappop(heap) count += e[0] #요청 처리 끝낸 후 answer += count - e[1] #현재 시각 - ..

1. 문제 2. 풀이 과정 방법 1) def solution(genres, plays): answer = [] hash1 = {} #장르별 분류 [재생횟수, 고유번호] 쌍을 저장 hash2 = {} #장르별 속한 노래들의 재생 수의 합 for i in range(len(genres)): #장르별 분류 if genres[i] not in hash1.keys(): hash1[genres[i]] = [] hash1[genres[i]].append([-plays[i], i]) #정렬하기 쉽게 재생 횟수를 -로 저장 #속한 노래들의 재생 수의 합 if genres[i] not in hash2.keys(): hash2[genres[i]] = 0 hash2[genres[i]] += plays[i] #합이 큰 순서대로..

1. 문제 *숫자들의 순서는 고정되어 있다고 생각해야 함. 2. 풀이 과정 방법 1) 1. 배열 정렬하기 => 필요 없는 연산 줄이기 위함 2. 초기설정 : Q를 초기화해 주는 것, 현재 index가 i인 값이 음수가 되어도 좌항의 합이 target값보다 크거나 같은 값만 Q에 넣는다. 3. Q에서 element를 하나 꺼내고 그 element에 기록된 index의 뒤의 값들이 또 음수가 되어도 좌항의 합이 target값보다 크거나 같은 값만 Q에 넣어준다. 4. Q의 element는 (음수 처리한 마지막 인덱스 값, 좌항의 합)로 구성되는데, 좌항의 합이 target이면 결과로 출력할 count += 1을 하고 다음 요소를 처리하러 간다. from collections import deque def s..

1. 문제 2. 풀이 과정 def solution(people, limit): answer = 0 people.sort() l = 0 r = len(people)-1 while l < r: #2명씩 타는 경우 count if people[l]+people[r]

1. 문제 2. 풀이 과정 방법 1) 시간 초과 number에서 k개를 뺏을 때 len(number) - k 길이의 수를 만들어야 한다. 이 조건에서 첫 번째 자리가 될 수 있는 수는 뒤에서 count 했을 때, 원하는 길이 이상인 값들이 그 후보이다. 최댓값과 그의 index값을 따로 찾는 데에 시간이 오래 걸렸다고 판단하였다. def solution(number, k): answer = '' pre_idx = -1 for i in range(1, len(number)-k+1)[::-1]: #이전에 선택한 값의 뒤부터 길이에 맞는 곳까지 중 최대값 찾기 answer += max(number[pre_idx+1:len(number)-i+1]) pre_idx = number[pre_idx+1:len(numb..

1. 문제 2. 풀이 과정 이 문제에서 답이 될 수 있는 후보는 두 가지이다. 1. 첫 번째는 단순히 index 0번에서 끝까지 차례대로 가면서 알파벳을 맞춰주는 것이다. 2. 두 번째는 제일 긴 A들의 연속을 피해서 둘러가는 것이다. A가 있는 건 굳이 갈 필요가 없는 곳이다. 제일 긴 A들의 연속만 피하고 짧은 A연속은 무시하는 이유는 예를 들어 설명하겠다. "KFPWAAAOFAAAAAALFJ"이라는 문자열이 입력으로 들어왔다고 할 때, 굵은 글자는 무조건 가야 하는 곳이다. OF로 가기 위해서는 짧은 A의 연속을 지나가는 것이 더 빠른 길이다. 정리하자면, A를 피해가는 방법 중에서는 제일 긴 A들의 연속을 피해 가는 것이 제일 빠른 방법이 된다. 또 여기서 "KFPWAAAOFAAAAAALFJ" 형..

1. 문제 2. 풀이 과정 방법 1) for문으로 자신보다 작은 수로 나눠지는지 하나씩 검사하여 소수를 판별하였다. def prime(n): #소수여부 검사 if n

1. 문제 2. 풀이 과정 방법 1) 이진탐색을 사용한다. 최소값 즉, start = 0이고 최대는 가능한 n편의 최대가 배열의 길이이므로 end = l로 설정하였다. def solution(citations): citations.sort() l = len(citations) s = 0 e = l #최댓값 while s