본문 바로가기

Programming

 (89)
[프로그래머스/Python] 큰 수 만들기(그리디) 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구해야한다. 1) 부르트 포스 당장 생각해볼 수 있는 방법은 k개의 수를 임의로 제거한 모든 경우의 수를 계산하고 그 중 가장 큰 수를 출력하는 것이다. 문제를 곧이곧대로 해석. 하지만 아래와 같이 풀면 시간초과가 난다. 그도 그럴 것이 number가 1,000,000자리까지 가질 수 있다. from itertools import combinations def solution(number, k): answer = '' number = list(map(''.join, combinations(number, len(number)-k))) return max(number) 2) 그리디 알고리..
[프로그래머스/Python] 피보나치 수(DP) bottom-up 방식으로 푸니까 풀린다. top-down(재귀+dp배열)으로 하면 왜인지 런타임에러가 난다.. 그리고 문제도 뭔가 헷갈리게 내놨음 import collections dp = collections.defaultdict(int) def fibo(n): global dp dp[0]=0 dp[1]=1 for i in range(2,n+1): dp[i]=(dp[i-1]+dp[i-2]) % 1234567 def solution(n): fibo(n) return dp[n]
[프로그래머스/Python] 타겟넘버(DFS) 전형적인 DFS 문제다. 그나저나 전역변수 쓰는법 몰라서 오래 걸렸다. answer = 0 def dfs(numbers, target, cnt, num): global answer if cnt == len(numbers): if num == target: answer+=1 return dfs(numbers,target,cnt+1,num+numbers[cnt]) dfs(numbers,target,cnt+1,num-numbers[cnt]) return def solution(numbers, target): global answer dfs(numbers, target, 0, 0) return answer
[프로그래머스/Python] K번째수(정렬) def solution(array, commands): answer = [] for i in commands: tmp = array[i[0]-1:i[1]] tmp.sort() answer.append(tmp[i[2]-1]) return answer
[프로그래머스/Python] 모의고사(단순구현) def correct_counter(supoza, answers): cnt=0 for i in range(len(answers)): if answers[i] == supoza[i%len(supoza)]: cnt+=1 return cnt def solution(answers): supoza1 = [1, 2, 3, 4, 5] supoza2 = [2, 1, 2, 3, 2, 4, 2, 5] supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] cnt=[] cnt.append(correct_counter(supoza1,answers)) cnt.append(correct_counter(supoza2,answers)) cnt.append(correct_counter(supoza3,answers))..
[프로그래머스/Python] 카펫(소인수분해) brown yellow 24 24 1. yellow가 만들어 낼 수 있는 모든 경우의 수를 탐색해야한다. -> 소인수분해로 만들 수 있는 사각형 찾아낸다. (1, 24) (2, 12) (3, 8) (4, 6) 2. 각 사각형에 대해서 테두리갯수를 구하고 brown이랑 같으면 그때의 사각형을 sort해서 return import math def get_divisor(num): divisors = [] length = int(math.sqrt(num))+1 for i in range(1,length): if num%i == 0: a =(i, num//i) divisors.append(a) return divisors def solution(brown, yellow): answer = [] tmp = get_..
[프로그래머스/Python] 완주하지 못한 선수(해쉬) 참가자들을 key값으로 등장횟수를 count해서 딕셔너리에 담아주는 Counter함수를 사용하자. 여기서 completion이 등장할 때마다 빼주면 마지막에 count=1인 놈이 혼자 남은 놈 import collections def solution(participant, completion): answer = '' dict_p = collections.Counter(participant) for i in completion: if i in dict_p: dict_p[i] -=1 for i in dict_p: if dict_p[i] == 1: answer = i return answer 더 짧게 풀 수 있네.. import collections def solution(participant, complet..
[프로그래머스/Python] 소수찾기(소수/순열/중복제거) from itertools import permutations def isPrime(num): if num < 2: return False for i in range(2,num): if num%i==0: return False return True def solution(numbers): answer = [] for k in range(1, len(numbers)+1): perlist = list(map(''.join, permutations(list(numbers), k))) for num in list(set(perlist)): if isPrime(int(num)): answer.append(int(num)) return len(set(answer))

티스토리툴바