프로그래머스

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/77486 문제 해설 Idea Union-Find 알고리즘의 Find() 함수를 사용하여 부모 노드에 대해 재귀적으로 접근 최악의 경우 O(NM)=10^10으로 시간 초과가 발생하지만, 매 탐색마다 최대 10,000원을 10씩 나눠 0이 되는 순간에 재귀가 종료되기 때문에 최대 깊이가 5로 좁혀짐 Time Complexity O(N) = 100,000 Data Size enroll, referral: str(10) * 10,000 seller: str(10) * 100,000 amount: int(100) * 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def find(parents, cur, income, answer): alloc = income//10 if parents[cur] == cur or alloc == 0: answer[cur] += income-alloc return answer[cur] += income-alloc find(parents, parents[cur], alloc, answer) return def solution(enroll, referral, seller, amount): N = len(enroll) answer = [0] * N name2id = {name:i for i,name in enumerate(enroll)} parents = [i if referral[i]=='-' else name2id[referral[i]] for i in range(N)] for i in range(len(seller)): find(parents, name2id[seller[i]], amount[i]*100, answer) return answer

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/68936 문제 해설 Idea Divide and Conquer 2차원 배열을 4등분씩 나눠 재귀함수를 호출하고 동일한 값으로 채워져 있는지 판단하여 값의 개수 증가 2^n 형태의 정수에 대해 NumPy를 활용해 행렬 인덱싱을 간단히 구현 Time Complexity O(N^2 Log N^2) = 20,000,000 Data Size arr: [[int(1)]], shape(2^n, 2^n) 1 <= 2^n <= 1024 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import numpy as np def quad_comp(n, arr, answer): values = np....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/87390 문제 해설 Idea Greedy n의 크기가 굉장히 크기 때문에 2차원 배열을 만드는 것만으로 시간 초과가 발생할 것을 예상 r행 c열의 값은 max(r,c)+1과 같고 1차원 배열의 인덱스 i에 대해 r은 i//n, c는 i%n와 동일 left부터 right까지의 인덱스를 규칙에 맞는 값으로 변환하여 반환 Time Complexity O(N) = 10^5 Data Size n: 1 <= int <= 10^7 left, right: 0 <= long <= n^2 right - left < 10^5 해설 코드 1 2 def solution(n, left, right): return [max(divmod(i,n))+1 for i in range(left,right+1)]

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17687 문제 해설 Idea Math 0부터 시작해 t*m의 길이를 만족하는 N진법 배열을 생성 매 순서마다 p 위치에 해당하는 값을 추출해 문자열로 반환 Data Size n: 2 <= int <= 16 t: 0 < int <= 1,000 m: 2 <= int <= 100 p: 1 <= int <= m 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 alpha = {10:'A',11:'B',12:'C',13:'D',14:'E',15:'F'} def n_base(num, base): result = str() while num > 0: num, mod = divmod(num, base) result += str(mod) if mod < 10 else alpha[mod] return result[::-1] def solution(n, t, m, p): arr = '01' total = t*m p = p%m i = 2 while len(arr) < total: arr += n_base(i, n) i += 1 answer = [t for i,t in enumerate(arr[:total]) if (i+1)%m==p] return ''....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238 문제 해설 Idea Binary Search answer에 대한 이진탐색 수행 (1 <= answer <= max(times)*n) 매 탐색마다 answer 시간 동안 심사관들이 심사할 수 있는 사람의 수를 계산 심사한 사람의 수가 n명 이상일 경우 최대 범위를 조정하고 재탐색 심사한 사람의 수가 n명 미만일 경우 최소 범위를 조정하고 재탐색 n명 이상의 사람을 심사할 수 있는 가장 작은 answer를 반환 Time Complexity Binary Search: O(M Log N^N) = 6,000,000 Data Size n: 1 <= int <= 1,000,000,000 times: int(1,000,000,000) * 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solution(n, times): answer = 0 start, end = 1, max(times)*n while start <= end: mid = (start+end)//2 passed = 0 for time in times: passed += mid // time if passed >= n: break if passed >= n: answer = mid end = mid-1 elif passed < n: start = mid+1 return answer