문제 - 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이 출력 - 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의 - 가로나 세로로 연결된 것은 연결이 된 것 - 대각선으로 연결이 된 것은 떨어진 그림 - 그림의 넓이란 그림에 포함된 1의 개수 해결방법 BFS를 활용하여 도화지를 탐색할 수 있도록 하였다. 상, 우, 하, 좌 순서로 각 위치에서 더 뻗어나갈 수 있는 위치를 탐색하였다. 뻗어나가면서 그림의 크기를 구해주었고, 최대 그림의 크기를 비교하면서 update 할 수 있도록 하였다. BFS 코드가 호출될 때는 그림 하나가 그려지는 것이기 때문에 BFS 함수 하단 부분에서 그림의 개수를 update 할 수 있도록 하였다. 코드 import java..
문제 - 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있음 - 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 것 - 각 줄에 연산을 나타내는 문자('D' 또는 'I')와 정수 n이 주어짐 - 'I n'은 정수 n을 큐에 삽입하는 연산 (동일한 정수가 삽입될 수 있음) - 'D 1'는 큐에서 최댓값 삭제 / 'D -1'는 큐에서 최솟값 삭제 (최댓값, 최솟값이 둘 이상인 경우 하나만 삭제 됨) - 큐가 비어있는데 적용할 연산이 'D'라면 무시 가능 - 모든 연산을 처리하고 최종적으로 큐에 저장된 데이터 중 최댓값과 최솟값 출력 해결방법 TreeMap 자료 구조를 활용하여 문제를 해결하였다. 숫자와 해당 숫자가..
getOrDefault(Object Key, V DefaultValue) - 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드 - Key : 값을 가져와야 하는 요소의 키 - DefaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값 사용 방법 import java.util.TreeMap; public class Main { public static void main(String arg[]) { int[] ex = {1, 2, 3, 1}; TreeMap treemap = new TreeMap(); for (Integer key : ex) treemap.put(key, treemap.getOrDefault(key, 0) + 1); System.out..
문제 - 현재 고속도로에 휴게소가 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) 이분 탐색을 통해 보석을..