여니손

문제 링크 : https://leetcode.com/problems/count-the-number-of-fair-pairs/description/🍊해결방법1lower와 upper 범위 내에서 두수의 합이 범위 안에 있는 쌍의 개수를 구하여라단 i 두개의 수가 필요하므로 for문 2개를 활용해보자범위가 최대 10^5 이므로 이진탐색을 활용하자nums를 오름차순으로 정렬lower를 만족하는 제일 왼쪽에 있는 lowIdxupper를 만족하는 제일 오른쪽에 있는 upIdx구해서 개수를 더해주자😀풀이import java.util.*;class Solution { public long countFairPairs(int[] nums, int lower, int upper) { // index의 ..

문제 링크 : https://leetcode.com/problems/most-beautiful-item-for-each-query/description/🍊해결방법queries에 있는 price보다 잦은 값 중에서 최대 beauty 값을 찾는 것이다items 배열을 정렬하자price를 오름차순으로 하면서 beauty는 내림차순으로 해서 beauty값을 계속 최대값으로 갱신하자queries의 price 값을 가지고 이진탐색을 통해 items에서 찾자😀풀이import java.util.*;class Solution { public int[] maximumBeauty(int[][] items, int[] queries) { // price순으로 오름차순을 하고 같은 가격일 때는 beauty..

문제 링크 : https://www.acmicpc.net/problem/1450🍊해결방법냅색문제라서 dp를 활용하려 했지만 2차원 배열에서 각각 최대 10억이라 메모리초과...모든 경우의 수를 따져보려 했지만 2^30이라 시간초과두 그룹으로 나눠서 합이 나올 수 있는 경우의 수를 각각의 리스트에 저장한개의 리스트만 정렬하여 이진탐색에 활용list1에 있는 모든 경우를 보면서 list2에서 이진탐색을 활용C이하의 무게를 만족하는 가장 큰 idx를 찾아 cnt 플러스😀풀이import java.io.*;import java.util.*;public class Main { static int[] arr; public static void main(String[] args) throws IOExce..

문제 링크 : https://www.acmicpc.net/problem/2295🍊해결방법세수의 합을 구하고 나서 그 합을 이진탐색으로 찾으려고 하면 N^3 을 시간초과두수의 합을 미리 구하자sum + arr[i] = arr[j] 이 조건을 만족하면 됨sum = arr[j] - arr[i] 이중 for문을 사용해서 조건을 구하고 sum을 이진탐색 돌면서 확인하자N^2으로 해결😀풀이import java.io.*;import java.util.*;public class Main { static int N; static int[] arr; static int max; public static void main(String[] args) throws IOException { ..

문제 링크 : https://www.acmicpc.net/problem/1208🍊해결방법모든 경우의 수를 확인하기에는 2^40으로 시간초과어차피 부분수열의 합을 찾는거기에 두 그룹으로 나누어서 합끼리 찾아보자두 그룹의 부분수열로 만들 수 있는 합을 각각의 List에 저장두개의 List에 M이 있는지 먼저 체크하나의 List를 정렬하여 이진탐색으로 합이 M이 되는걸 찾아보자이진탐색할 때 같은 값이 여러개 있을 수 있으니 lowerBound와 upperBound를 활용해서 구간을 찾자부분집합의 크기가 1이상인거를 조심하고, lowerBound와 upperBound 중 하나라도 못 M인 경우의 수 못 찾으면 스킵😀풀이import java.io.*;import java.util.*;public class M..

문제 링크 : https://www.acmicpc.net/problem/13397🍊해결방법M개의 구간의 모든 경우의 수를 다 구하고 최대 최소 하면 시간초과 발생정답은 0 ~ 배열의 최댓값 범위에서 존재이진탐색을 활용구간이 M개 보다 많이 생기면 값을 올리고구간이 M개 보다 적게 생기면 값을 내려서정답 출력😀풀이import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 0~배열의 최대값 이..

문제 링크 : https://www.acmicpc.net/problem/12015🍊해결방법DP를 활용하기에는 N이 100만이라 N^2 시간초과리스트를 통해 가장 긴 증가하는 부분 수열을 관리하자이진탐색을 활용하자리스트의 마지막 숫자가 num 보다 작다면 num 추가 해주기리스트의 마지막 숫자각 num 보다 크다면 이진탐색리스트에서 num 보다 크거나 같은 수 중에서 젤 최소 찾고 교체해주기😀풀이import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..

MediumIn the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.Rick stated that magnetic force between two different..

You are given an integer array bloomDay, an integer m and an integer k.You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it i..