WorkShop

※ 해당 문제의 링크는 여기입니다. ※ 3단계 문제인 만큼 굉장히 어려웠던 문제였습니다. 이번 글에는 제한 사항 대신 알고리즘 및 전체 코드만 포스팅하겠습니다. (제한 사항, 문제에 잘 적혀있는 데 또 적는 거 귀찮....) 알고리즘 가장 시간이 짧은 순서대로 일을 처리해야하는 것이 주 목적입니다.하지만 일은 한 번에 하나씩만 처리가 가능하므로일이 끝나고 나서 현재 시간때 이전에 들어온 일들 중 가장 시간이 짧은 것을 다음으로 일을 하며,하나 하나씩 처리해야하는 알고리즘을 가지고 있습니다. 단, 요청 시간. 즉, 언제 들어왔는 지 역시 파악해야하는 문제입니다. 전체 소스코드 import java.util.*; class Solution { public int solution(int[][] jobs) { ..

※ 해당 문제의 링크는 여기입니다. ※ 프로그래머스에서 설명되어 있듯이 "힙을 이용해서 우선순위 큐를 구현할 수 있습니다." 라고 설명되었있습니다. 우선순위 큐와 힙에 대해서 궁금하신 분들은 링크 참조해주세요. 제한사항 스코빌의 길이는 2이상 1000000 입니다. K는 0이상 1000000000 입니다. 스코빌의 원소는 각각 0이상 1000000 입니다. 모든 음식의 스코빌 지수를 K이상으로 만들 수 없다면 -1를 반환합니다. 문제는 레벨 2 치곤 꽤 쉬운 편입니다. (레벨 1에서 이상한 문제를 만난 적이 있어서 일종의 트라우마가 생겨버린 것 같기도;;) 그리고 효율성 테스트까지 있기때문에 시간복잡도도 적당히 꼬아야합니다. (재귀함수를 사용해서는 효율성 테스트를 통과하기 어렵다는 의미입니다.) 알고리즘..

우선순위 큐란, 기존 큐 방식인 FIFO 방식과 함께 우선순위를 정하여 해당 방향으로 정렬을 하는 큐라고 생각하시면 됩니다. 우선순위를 어떻게 지정하냐에 따라서 큐가 바뀝니다. 우선순위 큐는 대부분은 힙을 이용하여 구현합니다. 힙은 완전이진 트리 형태의 자료구조입니다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다는 장점이 있습니다. 그리고 이진 탐색 트리(BST)와 달리 중복 값을 허용합니다. 힙의 종류는 2가지 정도가 있는 데, 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다. 이 둘을 판단하는 기준은 아주 단순합니다. 부모 노드 ≥ 자식 노드 (즉, 부모 노드의 key 값이 자식 노드보다 크거나 같은 완전 이진트리) 라면, 최대 힙입니다. 그 반대라면 최소 힙입니다..