본문 바로가기

알고리즘/프로그래머스

 (29)
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 구명보트 (python) 풀이 def solution(people, limit): answer = 0 people.sort() frontIdx = 0 while people and frontIdx < len(people): leftLimit = limit leftLimit -= people.pop() answer += 1 try: if people[frontIdx]
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 큰 수 만들기 (python) 풀이 1 : 조합 (실패) from itertools import combinations def solution(number, k): numList = list(number) data = list(range(0, len(numList))) maxNum = 0 answer = '' delete = list(combinations(data, k)) for row in delete: tempList = numList.copy() for i in row: tempList[i] = '' tempNum = int(''.join(tempList)) if maxNum < tempNum: maxNum = tempNum answer = str(maxNum) return answer 조합으로 삭제 가능한 모든 인덱스 조합을..
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 조이스틱 (python) 풀이 def solution(name): answer = 0 minMove = len(name) - 1 for i, char in enumerate(name): answer += min(ord(char) - ord('A'), ord('Z') - ord(char) + 1) next = i + 1 while next < len(name) and name[next] == 'A': next += 1 minMove = min([minMove, 2 * i + len(name) - next, i + 2 * (len(name) - next)]) answer += minMove return answer 모범답안 참고 연속된 A를 찾고 이에 따른 최소 이동 길이를 찾으면 된다. enumerate를 사용하면 index와 배..
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 체육복 (python) 풀이 def solution(n, lost, reserve): lost = set(lost) reserve = set(reserve) for i in lost & reserve: lost.remove(i) reserve.remove(i) sorted_lost = sorted(lost) for i in sorted_lost: if i-1 in reserve: lost.remove(i) reserve.remove(i-1) elif i+1 in reserve: lost.remove(i) reserve.remove(i+1) return n - len(lost) 내 풀이 lost와 reserve는 중복이 없다고 했으므로 set으로 만든다. 둘의 교집합이 생기는 경우 자기 체육복을 입으면 되므로 교집합 먼저 처리해..
[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 이중우선순위큐 (python) 풀이 import heapq def solution(operations): answer = [] minheap = [] maxheap = [] for ins in operations: a, b = ins.split(' ') b = int(b) if a == 'I': #heapq에 push heapq.heappush(minheap, b) heapq.heappush(maxheap, -b) elif a == 'D': #heapq에 delete try: if b < 0: min_value = -(heapq.heappop(minheap)) maxheap.remove(min_value) else: max_value = -(heapq.heappop(maxheap)) minheap.remove(max_value) #h..
[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 더 맵게 (python) 풀이 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) try: while(scoville[0] < K): a = heapq.heappop(scoville) b = heapq.heappop(scoville) c = a + (2 * b) heapq.heappush(scoville, c) answer += 1 except: answer = -1 return answer 내 풀이 처음에 테스트 케이스 1, 3, 8, 14에서 런타임 에러가 났는데, 이는 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다." 제한 사항을 놓친 것이 원인이었다. 이는 try except문으로 구현하여 해결했..
[프로그래머스 코딩테스트 고득점 Kit / 정렬] H-Index (python) 테스트 케이스 citations return [7, 7, 7, 7, 7] 5 [7, 5, 5, 5, 4, 2, 1, 1, 0] 4 문제를 풀기 위해 이해해야 할 것: h의 최댓값은 citations의 길이이다. h값은 citations 배열의 요소에만 국한되지 않는다. 풀이 def solution(citations): answer = 0 citations.sort() h = len(citations) while(True): for i in range(len(citations)): if h
[프로그래머스 코딩테스트 고득점 Kit / 정렬] 가장 큰 수 (python) 풀이 def solution(numbers): answer = '' strNumbers = sorted(map(str, numbers), key=lambda x : x*3, reverse=True) answer = ''.join(strNumbers) if int(answer) == 0: answer = "0" return answer numbers 배열을 map을 사용하여 전부 str로 바꿔준다. 그리고 정렬을 하는데, 큰 수로 만들기 위해서는 내림차순 정렬을 해야한다. 따라서 reverse=True 조건을 사용한다. 내림차순 정렬만 적용하면 [3, 30, 33] 배열의 경우 [33, 30, 3] 이 나오는데 가장 큰 수가 되려면 [33, 3, 30]이 돼야한다. 따라서 람다식을 써서 조건을 더 추가해주..
반응형

티스토리툴바