본문 바로가기

전체 글

 (160)
[프로그래머스 코딩테스트 고득점 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..
[백준 / 누적 합] 11659 : 구간 합 구하기 4 (python) 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 예제 입력 5 3 5 4 3 2 1 1 3 2 4 5 5 예제 출력 12 9 1 풀이 import sys input = sys.stdin.readline() numNo, quizNo = map(int, input().s..
[프로그래머스 코딩테스트 고득점 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]이 돼야한다. 따라서 람다식을 써서 조건을 더 추가해주..
반응형

티스토리툴바