대학원생의 공부노트

프로그래머스의 파이썬을 무기로, 코딩테스트 광탈을 면하자!강의 5-7강을 정리한 글입니다. 5. 힙(Heap) 대표 문제 풀이: 더 맵게 문제: 더 맵게 최소, 최대 원소를 빠르게 꺼낼 수 있는 자료구조 → 힙! 복잡도: O(nlogn) import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while True: min1 = heapq.heappop(scoville) if min1 >= K: break elif len(scoville) == 0: answer = -1 break min2 = heapq.heappop(scoville) new_scoville = min1 + min2 * 2 heapq.heappush(scovill..

프로그래머스의 파이썬을 무기로, 코딩테스트 광탈을 면하자! 강의 1-4강을 정리한 글입니다. 1. 해시(Hash) 대표 문제 풀이: 완주하지 못한 선수 문제: 완주하지 못한 선수 동명이인이 나올 수 있다 → 이름이 몇 번 나왔는지 알 수 있는 자료구조가 필요 문자열로 접근할 수 있는 자료구조: 해시! 파이썬에서 해시는 딕셔너리로 구현됨 풀이1: 해시 해시로 이름과 등장 횟수를 세고, 다 돌은 후 value가 0이 아닌 key를 리턴한다. 복잡도: O(n) def solution(participant, completion): d = {} for x in participant: d[x] = d.get(x,0) + 1 #dictionary에 x가 있으면 그 값을 리턴하고, 없으면 0 리턴하고 1 더함 for ..