[2주차_목요일] 42626_더 맵게

[baexxbin]

• 사이트: 프로그래머스
• 문제: 더 맵게
• 번호: 42626
• 레벨: Level2

[baexxbin]

🤔 시간복잡도 고려사항

• 2<=scoville<= 1,000,000
• 0 <= K <= 1,000,000,000
• 0<= scoville의 원소 <= 1,000,000 이하
• O(N)이내로 해결하기

💡 풀이 아이디어

• 스코빌 지수가 가장 작은 값들로 진행 → 우선순위큐 사용

예외조건 -1 출력 조건 잘보기

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ scoville의 길이 ≤ 1,000,000 → 10^6이므로 O(nlogn)
• 우선순위 큐의 시간복잡도는 O(logn)

💡 풀이 아이디어

1. 우선순위 큐를 이용해서 최솟값 2개를 꺼내 공식대로 음식을 섞은 후 다시 큐에 넣으면서 카운팅
2. 더 이상 섞을 수 없을 경우에 카운트를 출력, 만약 큐의 최솟값이 K 미만이라면 -1을 출력

[yeongleej]

🤔 시간복잡도 고려사항

scoville 길이 <= 1,000,000 이므로 O(NlogN) or O(N) 생각

💡 풀이 아이디어

가장 맵지 않은 스코빌 지수를 계속 확인하고 가져와야 하므로 "우선위큐" 사용 우선순위 큐를 사용하면 O(logN)에 가져올 수 있음

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= scoville <= 1,000,000 이므로 O(logN)이나 O(N) 방법을 사용해야 함
• 우선순위 큐 사용
  • 우선순위 큐를 사용한다면 초기 입력은 Olog(N)으로, add, poll 연산은 O(1)으로 할 수 있음

💡 풀이 아이디어

1. pq에 초기 배열 원소들 push
2. while문을 통해 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복
   • pq.peek() >= K 이거나 pq.size() == 1이라면 break
   • poll연산을 통해 스코빌 지수가 가장 작은 값과 두번째로 작은 값을 뽑고 음식 만들고 다시 push

[icegosimperson]

🤔 시간복잡도 고려사항

• 2 <= scoville <= 1,000,000, O(N logN) or O(N)

💡 풀이 아이디어

• 스코빌 지수 : 가장 낮은 스코빌 지수, 두번째로 낮은 스코빌 지수 연산 -우선순위 큐를 이용하여 peek로 현재값과 K 비교 후 answer 증가

[yeahdy]

🤔 시간복잡도 고려사항 알고리즘: 우선순위 큐 시간복잡도: 2 <= scoville <= 1,000,000 크기로 O(NlogN)

💡 풀이 아이디어 두 수를 합친 후 스코빌 배열에서 오름차순 정렬이 되어야 하기 때문에 우선순위 큐를 사용해서 두수를 빼내고, 합친 수를 다시 넣도록 함 우선순위 큐는 기본적으로 원소를 오름차순 정렬하기 때문에 큐의 첫번째 원소가 K 보다 크거나 같다면 스코빌 모든 음식의 스코빌 지수가 K 이상 임