우선순위큐
-
[프로그래머스]셔틀버스 - JAVA문제풀이/프로그래머스 2021. 9. 4. 21:07
[프로그래머스]셔틀버스 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 풀이 🪑 문제 자체는 어렵지 않았으나 '시간'이라는 개념이 포함되서 시간 처리를 하는 방법이 익숙하지 않아 매우 어렵게 느껴졌던 문제였다! 시간 처리에서 막혀서 해설을 참고하였다. 📝 문제를 정리해 보자! 셔틀버스는 오전 9시부터 n회 t분 간격으로 역에 도착하며 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다. 9시에 도착한 셔..
-
[백준]13904: 과제 - JAVA문제풀이/백준 2021. 8. 5. 21:02
[백준]13904: 과제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 🪑 골드 문제 이길래 처음에 괜히 어렵게 생각해서 DP인가.. 했는데 그냥 구현문제였다. 📝 문제를 정리해 보자! 하루에 하나의 과제를 할 수 있다. 과제를 마무리 할 때마다 마무리한 과제의 점수를 얻는다. 🔧 문제를 풀어보자! 입력받은 과제들의 정보를 날짜 순서대로 내림차순 한다. 제일 마지막 날짜에서 부터 가능한 과제를 하나씩 우선순위 큐에 넣어준다. 우선순위 큐에서 가장 큰 점수를 갖는 과제를 하나씩 꺼내어 결과에 더해준다. 🙋♀️ 일단 예제를 함께 따라가 보자. 어떤 ..
-
[백준]22254:👨🔧공정 컨설턴트 호석 - JAVA문제풀이/백준 2021. 7. 29. 13:57
[백준]22254: 공정 컨설턴트 호석 22254번: 공정 컨설턴트 호석 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 $N$개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정 www.acmicpc.net 풀이 🪑 이전 문제가 너무 어려웠어서 잔뜩 쫄아있었는데 4번문제로 나왔던 이번 문제는 어렵지 않게 풀었다. 이분탐색 + 우선순위 큐(자료구조) 문제이다. 📝 문제의 조건을 살펴보자. 각 선물마다 제작에 필요한 시간이 정해져 있다. 1~K까지의 공정 라인에서 맞춤형 선물들을 제작하는데 소요되는 최소 라인의 수를 구한다. 🔧 문제를 풀어보자! 탐색 공정 개수를 기준값으로 이분탐색을 한다. mid개의 공정으로 맞춤형 선물..
-
[백준]22252:🕵️♂️ 정보 상인 호석 - JAVA문제풀이/백준 2021. 7. 27. 15:45
[백준]22252: 정보 상인 호석 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 풀이 🪑 우선순위큐, 해쉬맵을 활용한 자료구조 문제이다. 📝 문제의 조건들을 정리해 보자. 가치 순으로 가장 비싼 정보들을 구매한다. 한번 거래한 정보는 파기된다. 1로 시작하는 쿼리는 정보를 얻은 고릴라와 가지고 있는 정보 가치를 의미한다. 2로 시작하는 쿼리는 거래할 고릴라와 구매하려는 정보의 개수를 의미한다. 정보는 시간 순서대로 주어진다. 🤔 처음에는 문제가 잘 이해가 되질 않아 예제를 보며 따라가 보았다. 예제를 ..
-
[백준]1202: 보석 도둑 - JAVA문제풀이/백준 2021. 4. 27. 18:53
[백준]1202: 보석 도둑 www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선순위 큐를 사용한 문제로 굉장히 재미있게 느껴졌던 문제였다. 이 문제는 쉽게 생각하면 쉽게 풀 수는 있지만 시간복잡도에서 통과하기가 쉽지 않은 문제였다. 처음에는 우선순위큐를 사용하여 정렬을 통해 쉽게 풀 수 있을 것이라 생각했지만 역시나 시간 초과가 발생했다. 우선순위 큐를 두개를 만들어서 꺼내고 집어넣고를 반복..
-
[백준]1655: 가운데를 말해요 - JAVA문제풀이/백준 2021. 4. 27. 15:24
[백준]1655: 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 처음에는 우선순위큐를 사용해서 풀려다가 우선순위큐의 메소드 중에서는 인덱스로 접근할 수 있는 메소드가 없어 ArrayList로 접근하였다. list에 숫자를 입력받아 넣어주고 정렬 후에 2로나눈 인덱스 값을 출력하도록 하였더니 시간초과가 발생하였다. 다시 우선순위큐로 접근을 시도하였으나 마땅한 해결방법이 떠오르지 않았다. 다른 분들의 풀이를 확인하면서 정말..
-
[프로그래머스]야근 지수 - JAVA문제풀이/프로그래머스 2021. 3. 4. 13:53
문제 programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 works 배열의 원소에서 n만큼 뺀 값중 나머지에 대해 제곱의 합이 최소인 값을 찾는 문제이다. 제곱의 합이 최소가 되기 위해서는 works의 각 숫자들이 전체적으로 균형이 맞아야 한다. 예를 들어 첫 번째 예제 입력의 경우, works = {4, 3, 3}이고 n이 4이다. 이때 n시간을 모두 첫 번째 일을 처리하는데 사용하면 남는 시간은 0, 3..