나무 m미터가 필요 절단기의 높이를 이분탐색의 요소 범위가 20억 => long범위로 잡아야할듯? 마지막에 실험해보자
구현 방법
이분탐색을 위한 나무 요소중 max값 찾기
나무 윗동을 center값으로 잡고 자르기
잘랐을 때의 길이를 count로 체크
count가 m보다 크다면 height 최신화
count는 길이를 더해줘야하는데 길이의 범위가 20억이기 때문에 20억 이상이되는 수가 나올 것임. count ⇒ long선언
⇒
나무를 아껴서 가장 최소의 m만 챙겨야하기 때문에!!! 절단기 설정 높이는 높아야 하는 것 가장 높은 것을 기준으로 이분탐색
4 7
20 15 10 17
이 테스트케이스에서는 20이 가장 높다 -> 이분탐색의 범위를 1 ~ 20까지로 정함 중간부터 시작해서 쭉 돌려 만약에 범위안에 갯수가 맞다면 10 틀리면 왼쪽으로 가야겠지 => 이 높이에선 최소나무길이가 안맞기때문 맞으면 오른쪽으로 가야겠지 => 가장 조금 나무를 잘라야하니까
풀이
import java.io.*;
import java.util.*;
public class p2805 {
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 m = Integer.parseInt(st.nextToken());
int[] a = new int[n];
st = new StringTokenizer(br.readLine());
int right = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
a[i] = Integer.parseInt(st.nextToken());
right = Integer.max(right, a[i]);
}
int left = 1;
long height = 0;
while(left <= right){
long count = 0;
int center = (left + right) / 2;
//나무 윗동을 center값 기준으로 자르기
for(int i = 0; i < n;i++){
if(a[i] >= center){
count += a[i] - center;
}
}
if(count >= m){
height = center;
left = center + 1;
}else{
right = center -1;
}
}
System.out.println(height);
}
}
길이를 기준으로 이분탐색, 과자의 개수에 따라서 m명의 조카에게 나눠줄 수 있는지 판단하는 것이 중요!
구현 방법
이분탐색을 위한 범위
과자를 활용할 배열
⇒
배열로 과자를 입력받은 후 받은 과자 배열의 요소를 모두 탐색 → 이분탐색의 중앙값을 기준으로 해당 과자의 갯수를 카운트하고, 카운트의 갯수와 입력받은 m의 수가 일치한다면 과자를 동일한 길이로 줄 수 있는 것이기 때문에 해당 값을 정답에 저장 → 길이가 포함된다면 이분탐색 피벗기준 우측, 포함되지않으면 피벗기준 좌측
풀이
import java.io.*;
import java.util.*;
public class p16401_2 {
public static void main(String[] args) throws IOException{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] a = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++){
a[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(a);
int maxCookieLength = 0;
int left = 1;
int right = a[n-1];
while(left <= right){
int count = 0;
int center = (left + right) / 2;
//m을 기준으로 몇개가 나오는지 카운트
for(int i = 0; i <n; i++){
count += a[i]/center;
}
if(count >= m){
maxCookieLength = center;
left = center+1;
}else{
right = center-1;
}
}
System.out.println(maxCookieLength);
}
}
queue를 통해 각 요소를 소비하며 문자가 2개 이상일때는 그리디의 조건인 드래그 없는 문자만 삭제하는게 저렴한지, 드래그한 후에 삭제하는 것이 저렴한지 구분하며 각 에너지를 더해주고, 이후 HYU의 개수를 기준으로 H,Y,U중 수가 적은 것을 기준으로 HYU묶음 개수를 출력
묶음이 있어서 이번에 배워본 groupingBy를 활용했는데, 아마 더 상세하게 바꿀 수 있을 것 같은데 아직 많이 헷갈려서 제대로 활용은 못해봤다 아직은 사용하면서 익숙해지는데 더 힘을 써봐야겠다.
구현 방법
그리디 조건을 위한 문자 길이체크 count
HYU가 아닌 인덱스 위치를 담아둔 Queue
각 스트림 매핑 후 H,Y,U를 담기위한 Map
⇒
Queue의 값을 계속 체크하면서 인덱스 차이가 1 이상이면 범위가 벗어난 것 벗어난 범위 기준으로 {카운트 * d(각 문자를 개별딜리트)} vs {d + m} 비교 후 저렴한 것 선택 후 energe에 합치기
→ HYU매핑은 입력받은 문자열 그대로 다시사용해서 굳이 스트림 .chars로 변환 후 각 요소의 H,Y,U를 각각 맵에 담는 형식으로 구현
기존의 문자열에 .append로 HYU를 굳이 추가했는데 이유는 stream으로 매핑할때
아래의 반례는 Map 안에 H관련한 값만 생기기 때문이였다.
1
H
1 3
풀이
package Baekjoon.silver;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class p29812 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int energy = 0;
int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
sb.append(br.readLine()).append("HYU");
StringTokenizer st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
ArrayList<Map<Integer, int[]>> removeRange = new ArrayList<>();
Queue<Integer> noHYUList = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (!isHYU(sb.charAt(i))){
noHYUList.add(i);
}
}
boolean flag;
while(!noHYUList.isEmpty()){
flag = false;
final int firstIndex = noHYUList.poll();
int prevIndex = firstIndex;
int count = 1;
while(!noHYUList.isEmpty()){
int isContinuousIndex = noHYUList.peek();
if(isContinuousIndex-prevIndex == 1){
prevIndex = noHYUList.poll();
flag = true;
count++;
}else {
break;
}
}
if(!flag || count * d < m+d){
energy+= d*count;
}else{
energy += d + m;
}
}
Map<Integer, List<Integer>> result = sb.toString().chars()
.boxed()
.filter(c -> isHYU(c))
.collect(Collectors.groupingBy(c -> c));
int min = Integer.MAX_VALUE;
for(int num : result.keySet()){
min = Integer.min(result.get(num).size(), min);
}
sb = new StringBuilder();
if(energy == 0){
sb.append("Nalmeok");
}else{
sb.append(energy);
}
sb.append(System.lineSeparator());
if(min == 1 || Integer.MAX_VALUE == min){
sb.append("I love HanYang University");
}else{
sb.append(min-1);
}
System.out.println(sb);
}
static boolean isHYU(int a) {
switch (a) {
case 'H', 'Y', 'U':
return true;
default:
return false;
}
}
}
package Baekjoon.silver;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class p29812 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int energy = 0;
int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
sb.append(br.readLine()).append("HYU");
StringTokenizer st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
Queue<Integer> noHYUList = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (!isHYU(sb.charAt(i))) {
noHYUList.add(i);
}
}
boolean flag;
while (!noHYUList.isEmpty()) {
flag = false;
final int firstIndex = noHYUList.poll();
int prevIndex = firstIndex;
int count = 1;
while (!noHYUList.isEmpty()) {
int isContinuousIndex = noHYUList.peek();
if (isContinuousIndex - prevIndex == 1) {
prevIndex = noHYUList.poll();
flag = true;
count++;
} else {
break;
}
}
if (!flag || count * d < m + d) {
energy += d * count;
} else {
energy += d + m;
}
}
Map<HYU, Long> result = sb.toString().chars()
.filter(c -> isHYU(c))
.boxed()
.collect(Collectors.groupingBy((Integer c) -> HYU.valueOf(changeHYU(c)), Collectors.counting()));
int min = Integer.MAX_VALUE;
for (Object num : result.keySet()) {
min = Integer.min(Math.toIntExact(result.get(num)), min);
}
sb = new StringBuilder();
if (energy == 0) {
sb.append("Nalmeok");
} else {
sb.append(energy);
}
sb.append(System.lineSeparator());
if (min == 1 || Integer.MAX_VALUE == min) {
sb.append("I love HanYang University");
} else {
sb.append(min - 1);
}
System.out.println(sb);
}
static boolean isHYU(int a) {
switch (a) {
case 'H', 'Y', 'U':
return true;
default:
return false;
}
}
static String changeHYU(int c) {
return String.valueOf((char) c);
}
private enum HYU {
H,
Y,
U
}
}
후기
스트림 없이 하면 참 쉽겠지만… 언젠가는 잘 써보고싶어서 계속 활용하면서 일단 익숙해져야할것같다.. 이번에는 스트림을 리팩토링 후에 성능이 더 느려졌는데 아마 boxing하는 비용이 더 많아지고, 중간에 changeHYU를 통해 계속 값을 더해줘서 그럴 것 같았다.
