https://www.acmicpc.net/problem/3020
이분탐색임을 알고 있었고, 종유석, 석순 각각의 높이를 강의에서 따로 저장했던 기억이 있었음.
+ 직전에 이분탐색, lowerBound, upperBound 알고리즘을 이해 및 암기하였음
이를 바탕으로 문제 아이디어, 구현까지 전부 해냄.
다만, 종유석의 lowerBound구할 때 target으로 어떤 값을 넣어야할 지에 대해 한 번 틀려서 노트에 필기하면서 오류 찾아냄.
배열의 인덱스에 대해 안햇갈리게 지정하는 방법을 모색해야할 듯.
전반적으로 잘 풀었음!! GOOD
나중에 lowerBound, upperBound 코드 까먹지 않게 복습해야함.
<이분탐색 , lowerBound, upperBound 정리>
이분탐색은 해당 값 or target값 위치 아무 곳 반환
lowerBound는 target 이상의 값의 위치 중 가장 빠른 것 반환
upperBound는 target 초과의 값의 위치 중 가장 빠른 것 반환
차이점 | right 초기값 | while문의 조건 | while안의 첫번째 조건문 | 반환값 |
이분탐색 | N(배열 원소 끝) | left <= right (whie안에서 return하므로) |
- | mid |
lowerBound | N+1(배열 바깥) | left < right | if(target <= arr[mid]) (lowerBound는 target 이상의 위치를 return) |
left |
upperBound | N+1(배열 바깥) | left < right | if(target < arr[mid]) | left |
<내 정답 코드>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, H;
static int[] sucksoon;
static int[] jongyou;
static int min=987654, cnt=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
sucksoon = new int[N/2];
jongyou = new int[N/2];
for(int i=0; i<N; i++) {
if(i%2 == 0) {
sucksoon[i/2] = Integer.parseInt(br.readLine());
}
else {
jongyou[i/2] = Integer.parseInt(br.readLine());
}
}
Arrays.sort(sucksoon);
Arrays.sort(jongyou);
for(int h=1; h<=H; h++) {
int boom;
boom = N - (lowerBoundSucksoon(h) + lowerBoundJongyou(H-h+1));
// System.out.println("lowerBoundSuck = " + lowerBoundSucksoon(h) + "| lowerBoundJong = " + lowerBoundJongyou(H - h) + "| boom = " + boom);
if (boom < min) { // 만약 현재 높이의 박치기 개수가 최솟값보다 작으면
min = boom;
cnt = 0;
}
if (boom == min) {
cnt++;
}
}
System.out.println(min + " " + cnt);
}
static int lowerBoundSucksoon(int target) {
int left = 0;
int right = N/2;
int mid;
while(left < right) {
mid = (left + right) / 2;
if(target <= sucksoon[mid]) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
static int lowerBoundJongyou(int target) {
int left = 0;
int right = N/2;
int mid;
while(left < right) {
mid = (left + right) / 2;
if(target <= jongyou[mid]) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
/*
종유석 높이, 석순 높이 각각 저장해놓고
각 높이별로 개똥벌레가 몇개 뚫는지 계산
근데 높이가 5 * 10^5개임, 종유석_석순 개수가 2 * 10^5개임
단순 이중포문으로는 시간초과뜸.
종유석, 석순 각각 오름차순 정렬해놓고
높이별로 뚫는 개수 계산할 때 마지막인덱스 - lowerBound(현재 높이) 하면 현재높이 이상의 석순 개수가 나옴.
종유석 개수는 마지막인덱스 - lowerBound(H-현재높이) 하면 현재높이보다 낮은(그러니까 긴) 종유석 개수가 나옴
이렇게 하면, Hlog(N) + Nlog(N)으로 풀림
*/
}
'PS > 삼성SDS알고리즘특강' 카테고리의 다른 글
[SDS 알고리즘 특강 복습] 2042 구간 합 구하기 (인덱스트리) (0) | 2025.02.18 |
---|---|
[SDS 알고리즘 특강 복습] 7453 합이 0인 네 정수 (투포인터) (0) | 2025.02.18 |
[SDS 알고리즘 특강 복습] 1062 가르침 (DFS / 백트래킹) (0) | 2025.02.16 |
[SDS 알고리즘 특강 복습] 1103 게임 (DFS / 백트래킹 + dp) (0) | 2025.02.15 |
[SDS 알고리즘 특강 복습] 3055 탈출 (BFS) (0) | 2025.02.15 |
https://www.acmicpc.net/problem/3020
이분탐색임을 알고 있었고, 종유석, 석순 각각의 높이를 강의에서 따로 저장했던 기억이 있었음.
+ 직전에 이분탐색, lowerBound, upperBound 알고리즘을 이해 및 암기하였음
이를 바탕으로 문제 아이디어, 구현까지 전부 해냄.
다만, 종유석의 lowerBound구할 때 target으로 어떤 값을 넣어야할 지에 대해 한 번 틀려서 노트에 필기하면서 오류 찾아냄.
배열의 인덱스에 대해 안햇갈리게 지정하는 방법을 모색해야할 듯.
전반적으로 잘 풀었음!! GOOD
나중에 lowerBound, upperBound 코드 까먹지 않게 복습해야함.
<이분탐색 , lowerBound, upperBound 정리>
이분탐색은 해당 값 or target값 위치 아무 곳 반환
lowerBound는 target 이상의 값의 위치 중 가장 빠른 것 반환
upperBound는 target 초과의 값의 위치 중 가장 빠른 것 반환
차이점 | right 초기값 | while문의 조건 | while안의 첫번째 조건문 | 반환값 |
이분탐색 | N(배열 원소 끝) | left <= right (whie안에서 return하므로) |
- | mid |
lowerBound | N+1(배열 바깥) | left < right | if(target <= arr[mid]) (lowerBound는 target 이상의 위치를 return) |
left |
upperBound | N+1(배열 바깥) | left < right | if(target < arr[mid]) | left |
<내 정답 코드>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, H;
static int[] sucksoon;
static int[] jongyou;
static int min=987654, cnt=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
sucksoon = new int[N/2];
jongyou = new int[N/2];
for(int i=0; i<N; i++) {
if(i%2 == 0) {
sucksoon[i/2] = Integer.parseInt(br.readLine());
}
else {
jongyou[i/2] = Integer.parseInt(br.readLine());
}
}
Arrays.sort(sucksoon);
Arrays.sort(jongyou);
for(int h=1; h<=H; h++) {
int boom;
boom = N - (lowerBoundSucksoon(h) + lowerBoundJongyou(H-h+1));
// System.out.println("lowerBoundSuck = " + lowerBoundSucksoon(h) + "| lowerBoundJong = " + lowerBoundJongyou(H - h) + "| boom = " + boom);
if (boom < min) { // 만약 현재 높이의 박치기 개수가 최솟값보다 작으면
min = boom;
cnt = 0;
}
if (boom == min) {
cnt++;
}
}
System.out.println(min + " " + cnt);
}
static int lowerBoundSucksoon(int target) {
int left = 0;
int right = N/2;
int mid;
while(left < right) {
mid = (left + right) / 2;
if(target <= sucksoon[mid]) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
static int lowerBoundJongyou(int target) {
int left = 0;
int right = N/2;
int mid;
while(left < right) {
mid = (left + right) / 2;
if(target <= jongyou[mid]) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
/*
종유석 높이, 석순 높이 각각 저장해놓고
각 높이별로 개똥벌레가 몇개 뚫는지 계산
근데 높이가 5 * 10^5개임, 종유석_석순 개수가 2 * 10^5개임
단순 이중포문으로는 시간초과뜸.
종유석, 석순 각각 오름차순 정렬해놓고
높이별로 뚫는 개수 계산할 때 마지막인덱스 - lowerBound(현재 높이) 하면 현재높이 이상의 석순 개수가 나옴.
종유석 개수는 마지막인덱스 - lowerBound(H-현재높이) 하면 현재높이보다 낮은(그러니까 긴) 종유석 개수가 나옴
이렇게 하면, Hlog(N) + Nlog(N)으로 풀림
*/
}
'PS > 삼성SDS알고리즘특강' 카테고리의 다른 글
[SDS 알고리즘 특강 복습] 2042 구간 합 구하기 (인덱스트리) (0) | 2025.02.18 |
---|---|
[SDS 알고리즘 특강 복습] 7453 합이 0인 네 정수 (투포인터) (0) | 2025.02.18 |
[SDS 알고리즘 특강 복습] 1062 가르침 (DFS / 백트래킹) (0) | 2025.02.16 |
[SDS 알고리즘 특강 복습] 1103 게임 (DFS / 백트래킹 + dp) (0) | 2025.02.15 |
[SDS 알고리즘 특강 복습] 3055 탈출 (BFS) (0) | 2025.02.15 |