백준 1920
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int arr[] = new int [N];
StringTokenizer st;
st = new StringTokenizer(br.readLine());
for(int i = 0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
boolean find = false;
int target = Integer.parseInt(st.nextToken());
int start = 0;
int end = arr.length-1;
while(start <= end) {
int med = (start + end)/2;
int medV = arr[med];
if(medV > target) {
end = med-1;
}
else if(medV < target) {
start = med+1;
}
else {
find = true;
break;
}
}
if(find) {
System.out.println(1);
}
else {
System.out.println(0);
}
}
}
}
백준 2343
https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
틀린 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
int end = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
end+=arr[i];
}
Arrays.sort(arr);
int start = arr[N-1];
while(start <= end) {
int count = 0; //블루레이 개수 카운팅 변수
int sum = 0;
int med = (start+end)/2;
for(int i = 0; i < N; i++) {
if(sum+arr[i]> med) {
count++;
sum = 0;
}
sum += arr[i];
}
if(sum!=0) {
count++;
}
if(count > M) {
start = med+1;
}
else end = med-1;
}
System.out.println(start);
}
}
✅오답의 이유: 문제에서 주어진 ' 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. ' 라는 조건때문에 sort를 하면 강의의 순서가 뒤섞여 틀리게 된다.
Arrays.sort(arr);
int start = arr[N-1];
→ for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if(start<arr[i])
start=arr[i];
end+=arr[i]; }
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
int start = 0;
int end = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if(start<arr[i]) start=arr[i];
end+=arr[i];
}
while(start <= end) {
int count = 0; //블루레이 개수 카운팅 변수
int sum = 0;
int med = (start+end)/2;
for(int i = 0; i < N; i++) {
if(sum+arr[i]> med) {
count++;
sum = 0;
}
sum += arr[i];
}
if(sum!=0) {
count++;
}
if(count > M) {
start = med+1;
}
else end = med-1;
}
System.out.println(start);
}
}
⭐ ⭐ ⭐ 백준 1300 K번째 수
https://www.acmicpc.net/problem/1300
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
✅process
시간 복잡도가 N^2면 안된다. 구간의 길이가 N인 이중 for문을 쓰지 않고 문제를 푸는 방법을 생각해내야 함.
> 이분탐색을 사용해야겠구나.여기부터 생각해내기 어렵....ㅠㅠ
그리고, 굳이 이중 for문을 돌면서 이차원 A 배열에 값 저장을 하지 않아도 된다.
이 문제에서는 A 배열을 직접적으로 쓸 일이 없기 때문.
어떻게 하면 이중 for문을 쓰지 않고 이 문제를 풀 수 있을까?
일단 문제의 조건에서 A[i][j]=i*j이므로 A의 i번째 행은 i의 배수로 이루어져있음을 알 수 있다.
여기서 하나의 아이디어를 생각할 수 있다.
굳이 j를 쓰지 않아도 된다는 점. 행(i)을 기준으로 1~N까지 한번만 돌면서 B[k]를 구하면 된다.
또 하나 중요한 포인트가 있다.
A[][]배열을 B[]배열로 옮긴다고 상상해보자.
B[k]의 값이 k를 넘을 수 있는가? 즉, B[k] >= k 가 가능한가?
답은 false다. A의 각 열은 모두 배열의 행(i=1~N)의 배수이기 때문에 절대 k를 넘을 수 없다.
그렇다면... B[k]를 어떻게 찾아야할까?
1. B[k]보다 작은 수의 갯수는 k-1개여야 한다. 즉, B[]배열에서 k번째 수 앞에는 k-1개의 숫자가 있어야한다.(당연한 말)
2. 각 행에서 중앙값(med)보다 작은 수를 찾아 카운팅해주자.
예외 처리) 카운팅한 수가 N보다 크다면 값을 N으로 처리해주자. why? A의 사이즈가 N*N이므로.
3. 만약 med보다 작은 수가 k보다 작다면 start를 med+1로 업데이트하고, 그렇지 않으면(k보다 크거나 같으면) end를 med-1로 업데이트한다.
이 문제의 예시를 살펴보자. (N=3, k=7)
위 과정을 한번 수행했을 때의 중앙값, 즉 첫 중앙값은 4이다. med = 4
각 행을 돌면서 4보다 작은 수가 몇개 있는지 찾는다. Math.min(med/i, N);
*여기서도 반복문으로 값을 비교하는 것보다 Math.min을 사용하여 메모리 초과가 뜨는 위험을 방지한다.
4보다 작은 수가 6개 있으므로 4는 6번째 수보다 큰 수가 될 수 없다.
med보다 작은 수가 k보다 작으면 start = med + 1;
med보다 작은 수가 k보다 크거나 같으면 end = med - 1;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Integer.parseInt(br.readLine()); //3 -> 3*3
long k = Integer.parseInt(br.readLine()); //k=7 B[7]=?
long start = 1;
long end = k;
// 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.
//N^2가 불가능.
long answer = 0;
while(start <= end) {
long med = (start+end)/2;
int count = 0;
//행
for(int i = 1; i <= N; i++) {
count += Math.min((med/i), N);
}
if(count < k) {
start = med + 1;
} else {
answer = med;
end = med - 1;
}
}
System.out.println(answer);
}
}
백준 16564 히오스 프로게이머
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
//팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의
int X[] = new int[N];
for(int i = 0; i < N; i++) {
X[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(X);
long start = X[0];
long end = X[N-1] + K; //만들 수 있는 최대 레벨
long res = 0;
while(start <= end) {
long med = (start+end)/2;
long total = 0; //올린 레벨 수 K
for(int i = 0; i < N; i++) {
if(X[i] < med) {
total+=(med-X[i]);
}
}
if(total <= K) {
start = med + 1;
res = Math.max(res, med);
}
else {
end = med - 1;
}
}
System.out.println(res);
}
}
'Algorithms > study log' 카테고리의 다른 글
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |
---|---|
[백준 나무자르기] 이분탐색시 시작 혹은 끝 지점 설정하는 방법 (0) | 2024.01.17 |
[Algorithm] Greedy 그리디 알고리즘 (1) | 2023.12.27 |
[Algorithm] DFS, BFS (1) | 2023.12.22 |
[JAVA] 시뮬레이션,구현 (0) | 2023.12.01 |