1. 문제
-scoville 리스트에서 최소값이 K (스코빌 지수) 이상이어야한다.
=> 최소값이 K 이상이다. = 리스트 요소 모두 K 이상이다.-scovile 리스트 모든 요소가 K 이상이 될 때 까지,
최솟값 + 두번째 최소값*2 를 반복한 횟수를 카운트한다.
2. 해결방법
- 파이썬 heapq 사용
heaqp 사용한 이유는?
-파이썬은 최소힙을 제공한다.
-min(scoville) <= K 대소비교,
scoville의 최소값 2개 pop
이 과정을 반복하는데 있어 최소값을 계속 사용해야 하므로 heap 자료구조를 써보도록한다
시도1. (실패)
그런데..
코드는 맞는데 효율성이 떨어져 틀렸다고 나온다..
시도2. (정답)
if 문의 위치를 바꾸었더니
효율성 테스트 통과했다..
★ if문 위치만 바꿨는데 왜 효율성이 올라갔을까?
처음에는 코드를 다시 짜봐야하나 고민하다...
다른 예시코드를 보고..근데 나랑 코드가 거의 비슷한데..
그럼 뭐가 문제지 했다..
1) if a>= K break;
시도1 코드에서 최소값 scoville[0] >= K인지 확인하고
변수 a에 scoville 첫번째 원소를 pop 했다.
굳이 첫번째 원소 즉, scoville의 최소값을 2번 호출하게 되는 일이었다.
그래서 변수 a에 할당한뒤 k과 비교하는 if문을
하지만 이 조건문은 시도1, 시도2 효율성에 상관이 없다!!
2) scoville가 비어있는지 확인!
scoville는 무조건 원소 1개를 갖을 수 밖에 없다.
문제에 보면 1개 이상이며, 계산(a+b*2)를 하더라도 원소 1개를 무조건 갖기 때문이다.
그래서!
먼저 가장 최소값을 pop한 뒤 길이가 0이 되는 테스트케이스일 경우,
while true문을 끝까지 돌고 와야 하므로 비효율적일 수도 있겠다 생각했다..
그래서 empty check는 첫번째 요소를 pop한뒤 check 하도록 바꿔주었다.
나의 생각이므로 좀더 정확한 이유는 계속 찾아봐야겠다..
