정글에서 온 개발자

코드from collections import Counterimport mathdef solution(clothes): c = Counter(x[1] for x in clothes) product = math.prod(c[p]+1 for p in c) return product-1메인 아이디어는 각 파츠별로 안입은 것까지 포함해서 조합으로 경우의 수를 센 후, 하나도 안 입은 경우 1가지를 빼주는 것이다.count만 할 거라 hash count 특화 객체인 Counter를 활용했다.math.prod가 sum 처럼 iterable의 곱셈을 해줘서 활용했다.배운것들counter.values()counter의 값들을 가공할 필요 없이 바로 쓸 수 있다면, 이 속성을 활용해도 좋겠다.functo..

코드def solution(phone_book): book = set(phone_book) for num in phone_book: for i in range(1,len(num)): check = num[:i] if(check in book): return False return True입력:전화번호 수 1~1,000,000각 전화번호 길이 1~20접근만약 모든 숫자에 대해서 서로 비교를 하면 N^2이 나온다. 1e12가 되면서 백준 기준 1만 초 정도 걸릴 것 같다.문제 유형이 해싱이니, 해싱을 이용해야할 것 같은데 각 전화번호의 프리픽스를 해싱하는 것보다는 전화번호 자체를 해싱하면 좋을 것 같다.그럼 해싱한..

내 코드from collections import defaultdictdef solution(participant, completion): d = defaultdict(int) for p in participant: d[p]+=1 for c in completion: d[c]-=1 return [x for x in d if d[x]!=0][0]다른 사람 풀이Counter 객체를 썼는데 좋아보였다.파이썬 Counter 공식문서from collections import Counterdef solution(participant, completion): p = Counter(participant) c = Counter(completion) p-=c return [*p...

내 코드import heapqdef solution(word): D=[] def make(str1): if(str1!=''): heapq.heappush(D,str1) if(len(str1)==5): return for c in 'AEIOU': make(str1+c) make('') cnt=1 while(D[0]!=word): heapq.heappop(D) cnt+=1 return cnt재귀로 문자열을 만들었다.정렬을 해야하는데 O(NogN) 이 걸릴걸 우려해, 생성하면서 heap에 넣었다.heap에 넣는것도 O(logN)을 N 번 하므로 O(NlogN)이지만, 생성하면서..

내 코드 (입접 행렬)def solution(N, wires): T = [[False]*(N+1) for _ in range(N+1)] for u,v in wires: T[u][v] = True T[v][u] = True def dfs(V): visited=[False]*(N+1) visited[V]=True stk=[V] while stk: v = stk.pop() for i in range(1,N+1): if(T[v][i]==True and not visited[i]): visited[i]=True..

입력이 적고(8), 문제 자체가 대놓고 완전탐색이라고 써있기 때문에 딱히 그리디를 안 따지고 풀었지만, 좀 더 빠른 코드를 고민하면서 그리디를 생각해볼 수도 있다. 그리디로 풀 수 있을까?그리디의 두가지 조건최적 부분 구조 : 문제의 최종 해결책이 부분 문제의 최적 해로 구성되어야 한다.탐욕적 선택 속성 : 각 단계의 선택이 이후의 선택에 영향을 주지 않는다.최적 부분 구조적은 소모 피로도부터 들르기얼핏 생각하기에, 최대한 많이 들르려면 피로도가 적게 드는 것부터 가야 할 것 같다.반례: [[80,20],[50,40],[30,10]] K=802→0→1 순으로 들르려고 하면 0번째에 피로도가 모자라서 1개 밖에 못 들른다.많은 필요 피로도부터 들르기그렇다면 많은 피로도부터 들르면 괜찮을까?반례: [[80,..

다양한 전체 순회permutation가장 간단하게 순열을 사용할 수 있다.from itertools import permutationsdef solution(k, dungeons): mx = 0 for perm in permutations(dungeons, len(dungeons)): hp = k visit = 0 for need,cost in perm: if(hp >= need): visit+=1 hp-=cost else: break mx = max(mx,visit) return mxPermutation 직접 구현직접 ..

부끄럽지만 원래 코드def solution(brown, yellow): MAX = int(yellow**0.5) isPrime = [True]*(MAX+1) prime = [] isPrime[0],isPrime[1] = False,False for i in range(2,MAX): if(isPrime[i]): prime.append(i) for k in range(2*i,MAX+1,i): isPrime[k]=False m = 1 n = yellow while(yellow>2): for p in prime: if(yellow%p==0): ..

좋은 코드 훔쳐오기def solution(numbers): Num = set() def perm(pick,unpick): if(pick!=''): Num.add(int(pick)) for i in range(len(unpick)): perm(pick+unpick[i], unpick[:i]+unpick[i+1:]) perm('',numbers) Num-={0,1} for i in range(2,int(max(Num)**0.5)+1): Num-=set(range(i*2,max(Num)+1,i)) return len(Num)관전 포인트itertools의 permutation을 쓰지..

코드import randomA = 0 # 구간의 최소값B = 1000 # 구간의 최대값L = 100 # 배열 최대 크기def correct_solution(numbers): answer = numbers # 정답 코드 return answerdef my_solution(numbers): answer = numbers # 내 풀이 코드 return answer def generate_random_numbers(a,b,n): return [random.randint(a,b) for _ in range(n)]def compare_solution(numbers, i=0): result1 = correct_solution(numbers) result2 = my_sol..