Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- 브라이틱스 서포터즈
- 혼공
- 노코드AI
- 삼성SDS
- 포스코 청년
- 추천시스템
- 캐글
- 삼성 SDS
- 영상제작기
- 삼성SDS Brightics
- Brigthics를 이용한 분석
- 모델링
- 개인 의료비 예측
- 브라이틱스
- Brightics Studio
- 혼공머신
- Brightics
- 직원 이직여부
- 팀 분석
- 혼공머신러닝딥러닝
- 삼성 SDS Brigthics
- 데이터 분석
- Brigthics
- Brigthics Studio
- 포스코 아카데미
- 직원 이직률
- Brightics를 이용한 분석
- 혼공학습단
- 데이터분석
- 삼성SDS Brigthics
Archives
- Today
- Total
데이터사이언스 기록기📚
[프로그래머스] Level 2_더 맵게(힙) 본문
📌문제 유형
힙(Heap)
📌문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
📌나의 문제풀이
1차시도(정확성: 66.7, 효율성: 0, 합계 : 66.7)
def solution(scoville, K):
answer = 0
while scoville[0] < K:
# 스코빌 계산 후 값 넣기, 만든 값 삭제
new_score = scoville[0] + scoville[1] * 2
scoville.append(new_score)
scoville = scoville[2:]
# 스코빌 만든 횟수
answer += 1
# 스코빌 정렬
scoville.sort()
# 스코빌 만들 수 없는 경우 -> -1 내뱉기
if len(scoville) == 1:
if scoville[0] < K:
return -1
return answer
2차시도(정확성: 성공, 효율성:0, 합계: 76.2)
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # 최소값만 유효!!, 미리 생성한 리스트 힙 자료형으로 변경
while scoville[0] < K:
new_num = 0
min_num = heapq.heappop(scoville)
heapq.heapify(scoville)
second_num = heapq.heappop(scoville)
new_num = min_num + second_num * 2
heapq.heappush(scoville, new_num)
answer += 1
if len(scoville) == 1 and scoville[0] < K:
return -1
return answer
3차 시도(통과)
- heapq 사용
- heappop 사용하여 가장 작은 값, 두 번째 작은 값 찾기 -> 계산
- 스코빌 계산 후 넣기
- 스코빙 K이상으로 만들 수 없는 경우 -1 리턴
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # 최소값만 유효!!, 미리 생성한 리스트 힙 자료형으로 변경
while scoville[0] <= K:
new_num = 0
# 스코빌 계산 숫자 찾기
min_num = heapq.heappop(scoville)
second_num = heapq.heappop(scoville)
# 스코빌 계산 후 넣기
new_num = min_num + second_num * 2
heapq.heappush(scoville, new_num)
answer += 1
if scoville[0] < K:
# 스코빌 지수 K이상으로 만들 수 없는 경우
if len(scoville) == 1:
return -1
else:
continue
else:
return answer
📌다른사람들 풀이
1) 나의 풀이와 유사
import heapq as hq
def solution(scoville, K):
hq.heapify(scoville)
answer = 0
while True:
first = hq.heappop(scoville)
if first >= K:
break
if len(scoville) == 0:
return -1
second = hq.heappop(scoville)
hq.heappush(scoville, first + second*2)
answer += 1
return answer
2) 간단한 풀이
from heapq import heapify, heappush, heappop
def solution(scoville, K):
heapify(scoville)
for i in range(1000000):
try:
heappush(scoville, heappop(scoville)+(heappop(scoville)*2))
if scoville[0] >= K: return i+1
except:
return -1
📌리뷰
- 힙(heap) : 특정한 규칙을 가지는 트리
- 최댓값과 최솟값을 찾는 연산일 때 사용!
- 키 값의 대소관계는 부모-자식간에만 성립, 형제 노드 사이에서는 대소 관계 성립하지 않는다.
📌참고
- heapq 정리
[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기
힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대
littlefoxdiary.tistory.com
728x90
'Coding Test > 프로그래머스(Python)' 카테고리의 다른 글
[프로그래머스] Level 2_카펫(완전탐색) (0) | 2022.09.27 |
---|---|
[프로그래머스] Level 3_이중우선순위큐(힙) (0) | 2022.09.25 |
[프로그래머스] Level2_전화번호 목록(해시) (0) | 2022.09.24 |
[프로그래머스] Level2_위장(해시) (0) | 2022.09.24 |
[프로그래머스] Level 2_H-Index(정렬) (0) | 2022.09.22 |
Comments