문제 - 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있음 - 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 것 - 각 줄에 연산을 나타내는 문자('D' 또는 'I')와 정수 n이 주어짐 - 'I n'은 정수 n을 큐에 삽입하는 연산 (동일한 정수가 삽입될 수 있음) - 'D 1'는 큐에서 최댓값 삭제 / 'D -1'는 큐에서 최솟값 삭제 (최댓값, 최솟값이 둘 이상인 경우 하나만 삭제 됨) - 큐가 비어있는데 적용할 연산이 'D'라면 무시 가능 - 모든 연산을 처리하고 최종적으로 큐에 저장된 데이터 중 최댓값과 최솟값 출력 해결방법 TreeMap 자료 구조를 활용하여 문제를 해결하였다. 숫자와 해당 숫자가..
문제 - 현재 고속도로에 휴게소가 N개 있음 - 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어짐 - 지금 휴게소를 M개 더 세우려고 함(반드시 모두 지어야 함) - 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에 휴게소를 세울 수 없음 - 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 함 - 휴게소가 없는 구간의 최댓값의 최솟값 출력 해결방법 처음에는 휴게소가 없는 구간들을 정렬하고 큰 수부터 중간에다 휴게소를 세우는 방식으로 문제를 해결하려 했으나, 나머지 테케는 잘 통과했지만 첫 테케가 막혔다.. 이분 탐색으로 문제를 해결하였는데, 휴게소 위치들을 리스트에 담아두고 휴게소 사이에 이분 탐색으로 구한 그 구간의 길이만큼씩 휴게소를 배치한다면 몇개를 배치할..
문제 - 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시함 - 이때 각 문제에 데드라인을 정함 - 동호가 받을 수 있는 최대 컵라면 수 구하기 해결방법 문제에 따른 정보를 Homework class 형태로 입력받고 데드라인을 기준으로 정렬하였고, 데드라인이 같다면 컵라면을 더 많이 주는 순으로 정렬할 수 있도록 구성하였다. 풀 문제가 정해지면 noodles 리스트에 저장해주었다. noodles 리스트는 컵라면을 더 많이 받기 위해서 정렬을 할 수 있었으면 좋겠다는 생각에 우선순위 큐를 사용하였다. input 2 100 2 100 3 500 3 500 이렇게 주어진다고 하면, (2, 100), (2, 100), (3, 500)을 선택하는 것 보다 (2, 10..
문제 - N명의 스태프는 폐활량이 다 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간이 다양함 - 각 스태프가 풍선 하나를 만드는 시간 Ai를 알고 있을 때, 풍선 M개를 만들기 위해 필요한 최소의 시간은? 해결방법 풍선 하나를 만드는 데 가장 오래 걸리는 스태프가 M개를 다 만드는 것을 처음 시작으로 잡고 이분 탐색을 진행하였다. 해당 시간이 지났을 때, 몇개의 풍선을 불었는지 계산해보면서 이분 탐색을 진행하였다. 또, 자료형으로 틀렸다 !!!!! 자료형을 잘 생각하고 문제를 해결해야 할 것 같다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Except..
문제 - 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 말한 수 중에서 중간값을 말해야 함 - 그동안 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 함 - 백준이의 동생이 말해야 하는 수를 순서대로 출력 해결방법 처음에는 리스트에 백준이가 정수를 외칠 때마다 넣어주면서 정렬을 하고, 가운데 인덱스를 구해 해당 인덱스의 숫자를 출력하는 방식으로 문제를 해결하려 했었는데 시간초과가 났다. 구글링을 통해 우선순위 큐를 두개를 써서 숫자를 계속 정렬해가면서 값을 빠르게 찾아나갈 수 있는 방법을 찾았다. 우선순위 큐 두개를 활용한 방법으로 한개씩 번갈아가면서 숫자를 넣어주면서 자동 정렬될 수 있도록 하였다. 차례로 각각에 번갈아 숫자를 넣어주었지만, 순서대로 큐에 넣었던 것이기 때문..
문제 - 보석은 M가지로 서로 다른 색상 중 한 색상 - 모든 보석을 N명의 학생들에게 나누어 주려고 함 - 보석을 받지 못하는 학생이 있어도 됨 - 학생은 항상 같은 색상의 보석만 가져감 - 한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투함 - 이런 질투심을 수치화하는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수 - 질투심이 최소가 되게 보석을 나누어 주려고 함 (질투심의 최솟값 출력) 해결방법 이분 탐색 문제를 많이 풀어보고 싶어서 선택했던 문제였기 때문에 바로 이전에 포스팅한 문제와 문제 풀이 방식은 거의 유사했다. 더보기 2023.02.26 - [Algorithm/Baekjoon] - [백준] 16401번 과자 나눠주기 (JAVA) 이분 탐색을 통해 보석을..
문제 - 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 함 - 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 함 - M명의 조카가 있고 N개의 과작 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이 구하기 - 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없음 해결방법 처음에 문제를 꼼꼼히 읽지 않아서 틀렸습니다가 계속 떴었다... 과자의 길이가 속하는 범위만 주어졌었는데 왜 그렇게 문제를 읽었는지는 모르겠지만 L1~LN까지 크기 순서대로 정렬되어 주어진다고 생각하고 문제를 풀었다. 나중에 다시 보니 해당 부분이 문제였고 정렬하는 코드를 추가해주어서 이를 해결하였다. 전체적인 문제는 이분 탐색으로 해결하였고, 막대 과자의 길이를 이분 탐색으..
문제 - 집은 0번부터 M번까지 강을 따라 번호가 매겨져 있음 - 인접한 집 사이의 거리는 모두 1 킬로미터 - 상근이는 0번 집 거주. 보트를 이용하여 사람들 운송 - 저녁까지 M번 집으로 이동해야 함 - 상근이가 M번 집으로 가는 길에 사람들을 태워주려 함 - 상근이가 모든 사람을 데려다주고 M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값 구하기 해결방법 문제는 쉽게 접근할 수 있었지만 또 자료형 실수를 했다.. 그냥 맨날 int로 때려박는거 다 들킴.. 아무튼 문제로 돌아가면, 상근이가 0번에서 M번으로 이동하는 중에 사람들을 함께 운송하고 있는데, 0->M 이동하는 방향 대로 운송을 원하는 사람은 따질 필요가 없다. 어차피 가는 길에 얻어타는 느낌이니까..? 그래서 역주행을 원하는 사람들에 ..