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

1. 문제 2. 풀이 과정 방법 1) result 배열을 만들고 각 집을 털 때마다 자신보다 -2, -3인 지점으로부터 [시작점 포함한 경우, 포함하지 않은 경우] 두 값을 계산하여 저장한다. def solution(money): l = len(money) result = [[0, 0]] result.append([0, money[0]]) #시작점 포함, 시작점 포함X result.append([money[1], 0]) for i in range(3, l+1): temp = [0, 0] temp[0] = money[i-1] + max(result[i-2][0], result[i-3][0]) temp[1] = money[i-1] + max(result[i-2][1], result[i-3][1]) resul..

1. 문제 2. 풀이 과정 방법 1) BFS from collections import deque def solution(tickets): answer = [] #티켓을 출발점을 key로 저장 hash_map = {} for a, b in tickets: if a in hash_map: hash_map[a].append([a, b]) else: hash_map[a] = [[a, b]] def bfs(start): q = deque() #출발하는 지점의 티켓 넣기 for h in hash_map[start]: q.append([h]) while q: arr = q.popleft() #모든 티켓을 사용할 수 있는 경우 답에 추가 if len(arr)==len(tickets): temp = start for ..

1. 문제 2. 풀이 과정 방법 1) 필요한 부분만 보고 count def solution(m, n, puddles): answer = 0 arr = [[0]*(m) for _ in range(n)] #웅덩이는 -1로 표기 if puddles != [[]]: for x, y in puddles: arr[y-1][x-1] = -1 q = set() #중복 제거 q.add((0, 0)) arr[0][0] = 1 while q: temp = set() for a, b in q: if a == n-1 and b == m-1: return arr[a][b]%1000000007 #하 na = a + 1 if na < n and arr[na][b] != -1: arr[na][b] += arr[a][b] temp.ad..

1. 문제 2. 풀이 과정 방법 1) N을 한 개 사용할 때부터 8개까지 사용할 때까지 돌면서, 찾는 값이 나오면 종료한다. 1개일 때 : N(1) 2개일 때 : N(1) + 연산자 + N(1) 3개일 때 : N(1) + 연산자 + N(2), N(2) + 연산자 + N(1) ... 여기서 연산자가 +, *일 때는 연산자 기준으로 좌우가 바뀌어도 같은 값이지만 -, //는 다른 값이 나올 수 있어서 추가로 고려해주어야 한다. def solution(N, number): answer = 0 arr = [] for i in range(1, 9):#사용하는 N의 수 temp = set() #중복제거를 위해 집합 사용 temp.add(int(str(N)*i)) #5, 55, 555 for j in range(1,..

1. 문제 2. 풀이 방법 방법 1) 시작점을 기준으로 오름차순 정렬 def solution(routes): answer = 0 routes.sort() s = -300000 e = 30000 for route in routes: #범위에 교집합이 있으면 범위를 교집합으로 설정 if s

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..