도메인은 특정한 주제나 분야에 대한 지식이나 활동을 가리키는 일을 뜻하는데,
특정 도메인을 전문적으로 사용하되, 이해하기 쉽고, 사용하기 쉬울 수 있도록 개발된 언어

장점

• 런타임 오버헤드를 발생시키지 않음
• 외부 DSL 사용 시 플랫폼에 자유로워짐

단점

• 개발 비용이 비쌈

⇒ 우리가 클린코드를 지향하는 이유와 DSL이 나온 이유가 같다고 생각함

DSL의 예시

• SQL (데이터베이스 질의 언어)
• Gradle (빌드 자동화 도구)
• Query DSL
• 자바의 Stream API

참고

https://www.jetbrains.com/ko-kr/mps/concepts/domain-specific-languages/

모던 자바 인 액션

올해 처음 접해봤는데, 실제 코딩 테스트와 유사한 방식으로 진행되어서 코테 준비할 때 도움이 많이 되는 것 같습니다!

백준 싫은데요

https://www.acmicpc.net/problem/25916

접근 방식

전형적인 투 포인터 형태로 햄스터의 몸집을 구멍을 막았을 때 구멍의 크기m에 최대한 가까운 수를 찾아 출력하는 문제

구현 방법

• 탐색 했을 때 최대값을 찾을 max값
• 누적합을 계산해 줄 count
• 투 포인터에 활용할 left, right

⇒ while문 안에서 count의 값이 m보다 크면 left의 값을 count에서 뺀 후 left++, count의 값이 m보다 작거나 같으면 right의 값을 count에 더한 후 right++ 이 때 max의 값와 카운트의 값을 비교해 최댓값을 갱신

풀이

import java.io.*;
import java.util.*;

public class p25916 {
    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());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        //8 10
        //2 2 2 2 11 2 5 2
        //9

        int left = 0;
        int right = 0;
        int max = Integer.MIN_VALUE;
        int count = 0;
        while (right < n) {
            if (count +a[right] <= m) {
                count += a[right];
                max = Integer.max(max, count);
                right++;
            }else{
                count -= a[left];
                left++;
            }
        }

        System.out.println(max);

    }
}

후기

투 포인터에 익숙해지기 좋은 문제였다

백준 계란으로 계란치기

https://www.acmicpc.net/problem/16987

백준 골드5 계란으로 계란치기

접근 방식

Egg 클래스를 선언해서 왼쪽부터 순서대로 들어서 해결

모든 경우의 수를 탐색해야 하기에, 백트래킹으로 진행

구현 방법

• Egg클래스
  • isBroken : 깨져있는지 확인
  • breakEgg : 대상이 깨져있는지 확인 후 공격
  • attackEgg : 서로 공격
• 깊은 복사를 위한 deepCopy 메서드
• 백트래킹

⇒

알을 꺼내는 방식은 순차적
꺼낸 알을 갖고 모든 알들에 시도해보기 (모든 경우의 수 탐색)
이후 최종 깊이에 도달하면 Egg의 깨져있는 수를 카운트

풀이

package Baekjoon.gold;

import java.io.*;
import java.util.*;

public class p16987 {

    static int n;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        ArrayList<Egg> eggList = new ArrayList<>();
        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            eggList.add(
                    new Egg(
                            Integer.parseInt(st.nextToken()),
                            Integer.parseInt(st.nextToken())
                    )
            );
        }

        if (n == 1) {
            System.out.println(0);
            return;
        }
        boolean[] visited = new boolean[n];
        dfs(eggList, 0, 0);

        System.out.println(max);

    }

    public static void dfs(List<Egg> prevEggList, int index, int depth) {
        if (depth == n) {
            //전체 브로큰 횟수 출력
            max = Integer.max(brokenCount(prevEggList), max);
            return;
        }

        for (int i = 0; i < n; i++) {
            List<Egg> nowEggList = deepCopy(prevEggList);
            Egg nowEgg = nowEggList.get(depth);
            if (i != depth) {
                nowEgg.breakEgg(nowEggList.get(i));
                dfs(nowEggList, 0, depth + 1);
            }
        }

    }

    static int brokenCount(List<Egg> eggList) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (eggList.get(i).isBroken()) {
                count++;
            }
        }
        return count;
    }

    static class Egg {
        int durability;
        int weight;

        Egg(int durability, int weight) {
            this.durability = durability;
            this.weight = weight;
        }

        public void breakEgg(Egg egg) {
            if (!egg.isBroken() && !this.isBroken()) {
                attackEgg(egg);
            }
        }

        private void attackEgg(Egg egg) {
            int a = this.weight;
            int b = egg.weight;
            this.durability -= b;
            egg.durability -= a;
        }

        private boolean isBroken() {
            if (durability <= 0) {
                return true;
            }
            return false;
        }

    }

    public static List<Egg> deepCopy(List<Egg> eggList) {
        ArrayList<Egg> tempList = new ArrayList<>();
        for (int i = 0; i < eggList.size(); i++) {
            Egg temp = eggList.get(i);
            tempList.add(new Egg(temp.durability, temp.weight));
        }
        return tempList;
    }
}

후기

문제 구현이 생각보다 어려웠는데 이유를 모르겠음…
굳이 이유를 꼽자면 Egg의 상태를 확인해줄 때 헷갈렸던 것 같다.

속도는 클래스를 활용해서 그런지 상당히 느림 매번 깨져있는지 확인하면서 더 돌아서 느린듯?

백준 문자열 잘라내기

https://www.acmicpc.net/problem/2866

접근 방식

문제 이해가 엄청 오래 걸렸던 문제..

1000의 범위이기에 Set만 사용해서 처리해도 풀리는 문제 But 공부하기 위해 이분탐색으로 구현!
각 행을 지울 때 마다 바뀌는 세로문자열에 중복값을 있는지 없는지 찾는 문제

구현 방법

• 세로 문자열 전체를 크게 저장할 StringBuilder[] 배열
• 중복체크를 위한 Set자료구조
• 중복에 걸린 것을 확인하기 위한 boolean값 flag

⇒ center는 행의 수라는 ****점을 확실하게 인지하고 진행한다면 할만할 것
행의 수를 center로 잡고 중복 값이 걸렸다면 행이 잘리기 이전 값도 똑같이 중복이란 점을 생각 →

flag 작동 시 right = center - 1;

flag 미작동 시 중복이 걸리지 않았기 때문에 left = center + 1;

풀이

package Baekjoon.gold;

import java.io.*;
import java.util.*;

//행을 지울때 마다 그 때의 세로문자열들 중에 중복값이 있느냐
public class p2866 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        char[][] a = new char[r][c];

        for (int i = 0; i < r; i++) {
            a[i] = br.readLine().toCharArray();
        }

        StringBuilder[] sb = new StringBuilder[c];

        for (int i = 0; i < c; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < r; j++) {
                sb[i].append(a[j][i]);
            }
        }

        if (r == 2) {
            System.out.println(0);
            return;
        }

        int left = 0;
        int right = r;
        int minValue = Integer.MAX_VALUE;
        boolean flag;
        //center는 행의 수
        while (left <= right) {
            flag = false;
            int center = (left + right) / 2;
            Set<String> set = new HashSet<>();
            for (int i = 0; i < c; i++) {
                String s = sb[i].substring(center, r);
                if (!set.add(s)) {
                    minValue = center;
                    flag = true;
                }
            }

            if (flag) {
                right = center - 1;
            } else {
                left = center + 1;

            }
        }
        if (minValue == Integer.MAX_VALUE) {
            System.out.println(0);
        } else {
            System.out.println(minValue - 1);
        }
    }
}

후기

의외로 이분탐색의 아이디어보다 문제 이해하는데 더 힘들었던 문제… 이분탐색인걸 알고 풀어서 그런 것 같긴 하다. 또 Set만을 사용해도 풀리는 것을 확인했는데 효율이 매우 좋지 않았었음

Chapter06 스트림으로 데이터 수집

6장에 들어가며..

이번 장의 초점은 최종 연산인 collect에 맞춰져 있다.

맛보기 - 통화별로 트랜잭션을 그룹화한 코드

<명령형 프로그래밍>
Map<Currency, List<Transaction>> transactionsByCurrencies = new HashMap<>();

for(Transaction transaction : transactions) {
    Currency currency = transaction.getCurrency();
    List<Transaction> transactionsForCurrency = transactionsByCurrencies.get(currency);
    if(transactionsForCurrency == null){
        transactionsForCurrency = new ArrayList<>();
        transactionsByCurrencies.put(currency, transactionsForCurrency);
    }
    transactionsForCurrency.add(transaction);
}

->

<함수형 프로그래밍>
Map<Currency, List<Transaction>> transactionsByCurrencies =
      transactions.stream().collect(Collectors.groupingBy(Transaction::getCurrency));

collect메서드를 통해 Collector 인터페이스를 사용하는데, groupingBy를 이용해서 각 키 버킷, 키 버킷에 대응하는 요소 리스트를 값으로 포함하는 맵이 만들어지게 된다.

Collect

• 스트림에서 지원하는 메서드
• collect(리듀싱)
• collect(Collector인터페이스 사용)

Collector

• 인터페이스
• 리듀싱 연산이 수행
• 스트림의 요소를 어떤 식으로 도출할지 지정

Collectors

• 유틸리티 클래스
• 정적 팩토리 메서드
• 기능
  • 스트림 요소를 하나의 값으로 리듀스하고 요약
  • 요소 그룹화
  • 요소 분할

리듀싱과 요약

스트림.collect를 통해 스트림의 모든 항목을 하나의 결과로 합칠 수 있다.

Collectors.maxBy, minBy - 스트림 값에서 최댓값과 최솟값 검색

Comparator<Dish> dishCaloriesComparator = Comparator.comparingInt(Dish::getCalories);

Optional<Dish> mostCalorieDish =
menu.stream()
    .collect(
        Collectors.maxBy(dishCaloriesComparator)
    );

• Optional반환
• 객체의 숫자 필드의 합계나 평균 연산 ⇒ 요약 연산

요약 연산

• Collectors.summingInt, double, long
• averagingInt, double, long
• summarizingInt
  • count, sum, min, average, max
  • getter

IntSummaryStatistics menuStatistics = menu.stream()
                      .collect(
                          Collectors.summarizingInt(Dish::getCalories)
                      );

Collectors.joining - 문자열 연결

• 각 객체에 toString메서드를 호출해서 모든 문자열을 하나의 문자열로 연결해서 반환
• StringBuilder가 활용됨

Collectors.reducing - 범용 리듀싱 요약 연산

• 모든 컬렉터는 reducing 팩토리 메서드로도 정의가 가능하다. 하지만, reducing이 아닌, 다른 팩토리 메서드를 사용하는 이유는 편의성 때문이다.

<인수가 3개인 reducing>
int totalCalories = menu.stream()
            .collect(Collectors.reducing(
                0, Dish::getCalories, (i, j) -> i + j)
            );

<인수가 1개인 reducing>
Optional<Dish> mostCalorieDish = menu.stream()
                     .collect(Collectors.reducing(
                         (d1, d2) ->
                             d1.getCalories() > d2.getCalories() ? d1 : d2)
                     );

• reducing에 들어가는 인수 3개
  • seed(identity)
  • mapper(Function)
  • BinaryOperator
• reducing에 들어가는 인수 1개
  • Optional반환 → 최소 2개 이상의 값이 필요하기 때문에
  • 첫번째 스트림 요소 = seed(identity)
  • 두번째 요소부터 BinaryOperator(seed, nextStream)

collect vs reduce

collect는 위에서 설명했던 것처럼 스트림의 요소를 어떤 식으로 도출할지 지정하는 특성을 갖고 있다. 즉 도출하려는 결과를 누적하는 컨테이너를 바꾸도록 설계되어 있는 가변형 메서드인 반면에 reduce는두 값을 하나로 도출하는 불변형 연산 이라는 점에서 의미론 적인 문제가 일어난다. 또 7장에서 다루는 병렬 처리 관련해서도 문제가 발생할 수 있다.

컬렉션 프레임워크 유연성 : 같은 연산도 다양한 방식으로 수행할 수 있다.

but 위에서 말했던 collect와 reduce처럼 용도에 맞는 형식으로 최대한 구현하는 것을 권장한다.

자신의 상황에 맞는 최적의 해법 선택

위에서 말했듯 컬렉션 프레임워크의 유연성 때문에 다양한 방식으로 동일한 결과를 낼 수 있지만, 방법에 따라 성능의 차이나 가독성의 문제가 생길 수 있다. 예를들면 reduce연산을 통해 누적 값을 검색하는 것이 아니라 mapToInt를 통해 IntStream으로 변환 후 .sum을 한다면 언박싱을 할 필요가 없어지므로 성능 향상을 볼 수 있을 것이다.

Collectors.groupingBy - 그룹화

<Type 기준으로 분류>
Map<Dish.Type, List<Dish>> dishesByType = menu.stream()
                          .collect(Collectors.groupingBy(Dish::getType));

<조건 기준 분류>
public enum CaloricLevel { DIET, NORMAL, FAT }

Map<CaloricLevel, List<Dish>> dishesByCaloricLevel =
menu.stream()
    .collect(
        groupingBy( dish -> {
                if (dish.getCalories() <= 400) return CaloricLevel.DIET;
                else if (dish.getCalories() <= 700) return CaloricLevel.NORMAL;
                else return CaloricLevel.FAT;
            }));

• Dish.Type.values()을 통해 키값이 생성된다고 생각하면 되고, 이를 분류 함수(classification function)라고 부른다.
• 각 키를 기준으로 분류를 할 수 있다.
  • 위의 값들을 기준으로 좀 더 명확히 하기 위해 설명하자면
    List리스트에 있는 Dish::getType을 통해 Map<K, V>가 설정되며, K가 Dish::getType의 반환타입, V는 해당 객체 자체를 List에 담아 저장하는 것을 의미한다.

그룹화된 요소 조작

Collectors.filtering

Map<Dish.Type, List<Dish>> caloricDishesByType = 
menu.stream()
    .collect(groupingBy(Dish::getType,
        Collectors.filtering(dish -> dish.getCalories() > 500, toList())));

Collectors.mapping

Map<Dish.Type, List<Dish>> caloricDishesByType = 
menu.stream()
    .collect(groupingBy(Dish::getType, mapping(Dish:getName, toList())));

Collectors.flatMapping

Map<Dish.Type, List<Dish>> caloricDishesByType = 
menu.stream()
.collect(groupingBy(
        Dish::getType,
        flatMapping(dish -> dishTags.get(dish.getName()).stream,
        toSet())));

컬렉터 결과를 다른 형식에 적용하기

Optional같은 반환타입이 들어왔을 때 해당 값이 있다는 것을 보장한다면 고려할 수 있는 방법

.collect(groupingBy(Dish::getType, -> 분류함수
    collectingAndThen(maxBy(comparingInt(Dish::getCalories)), -> 컬렉터래핑
    Optional::Get))); -> 변환함수

컬렉션 형식을 바꾸는 방법

toCollection(HashSet::new); → TreeSet등 변환이 가능

partitioningBy - 분할

• 분할은 특수한 종류의 그룹화
• 분할은 분할 함수(partitioning function)라 불리는 프레디케이트
• 맵의 키 형식은 Boolean
• 한개의 인수를 받을 때
  • true false기준으로 구분
• 두개의 인수를 받을 때
  • 다중 맵으로 필터링할 수 있음
  • Map<Boolean, Map<Dish.Type, List<Dish>>> vegetarianDishesByType = menu.stream() .collect(partitioningBy( Dish::isVegetarian, ->true false groupingBy(Dish::getType)->Type별로 또 나눔 ));

분할의 장점

• 참, 거짓 두 가지 요소의 스트림 리스트를 모두 유지하는 것이 장점
• 때문에 분류 목록을 만들 때 활용하기 좋다

Collector 인터페이스

Collector 인터페이스는 리듀싱 연산을 어떻게 구현할지 제공하는 메서드 집합으로 구성된다.

Collector<T, A, R> 인터페이스의 시그니처

• T는 수집될 스트림 항목의 제네릭
• A는 누적자, 중간 결과를 누적하는 객체
• R은 수집 연산 결과 객체의 형식

Collector 인터페이스의 메서드

• Supplier<A> supplier()
  • 새로운 결과 컨테이너 만들기
  • 빈 누적자(seed) 인스턴스 만들기
  • ex) return () → new ArrayList();
• BiConsumer<A, T> accumulator()
  • 결과 컨테이너에 요소 추가하기
  • 리듀싱 연산을 수행하는 함수를 반환
  • n번째 요소를 탐색할 때 두 인수, 누적자와 n번째 요소를 함수에 적용한다.
  • A → 누적자 T를 A에 반영한 후 반환
  • ex) return List::add; or return (list, item) → list.add(item);
• Function<A, R> finisher()
  • 최종 변환값을 결과 컨테이너로 적용하기
  • 누적자 객체를 최종 결과로 변환
• BinaryOperator<A> combiner()
  • 두 결과 컨테이너 병합
  • 병렬 처리된 누적자를 결합하는 메서드
• SET<Characteristics> characteristics()
  • collect 메서드가 어떤 최적화(ex : 병렬화)를 이용해서 리듀싱 연산을 수행할 것인지 결정하도록 돕는 힌트
  • Characteristics은 각 특성을 담고있는 Enum 을 넣어서 힌트를 제공.
    • UNORDERED - 방문 순서나 누적 순서에 영향을 받지 않는다.
    • CONCURRENT - 다중 스레드에서 accumulator 함수를 동시에 호출할 수 있으며 병렬 리듀싱이 수행 가능하다.
    • IDENTITY_FINISH - 리듀싱 과정의 최종 결과에 누적자 객체를 바로 사용할 수 있는 것

응용하기

직접 List를 담는 ToListCollector를 구현해보자

//<version1 직접 interface 구현체 만들기>
import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;

public class ToListCollectorTest<T> implements Collector<T, List<T>, List<T>> {

    @Override
    public Supplier<List<T>> supplier() {
        return ArrayList::new;
    }

    @Override
    public BiConsumer<List<T>, T> accumulator() {
        return List::add;
    }

    @Override
    public BinaryOperator<List<T>> combiner() {
        return (list1, list2) -> {
            list1.addAll(list2);
            return list1;
        };
    }

    @Override
    public Function<List<T>, List<T>> finisher() {
        return Function.identity();
    }

    @Override
    public Set<Characteristics> characteristics() {
        return Collections.unmodifiableSet(EnumSet.of(Characteristics.IDENTITY_FINISH, Characteristics.CONCURRENT));
    }
}

-----------------------------------------

//<version2 간단한 리듀싱은 구현체 필요없음>
List<Dish> dishes = menuStream.collect(
        ArrayList::new,
        List::add,
        List::addAll
);

6장을 마치며

• collect는 스트림의 요소를 요약 결과로 누적하는 다양한 방법을 인수로 갖는 최종 연산이다.
• Collectors라는 Collector구현체를 통해 다양한 리듀싱 연산을 손쉽게 할 수 있다.
• groupingBy, partitioningBy로 스트림의 요소를 그룹화,분할할 수 있다.
• 다수준의 그룹화, 분할, 리듀싱 연산에 특화되어있다.
• Collector 인터페이스를 직접 구현해 커스텀 컬렉터를 개발, 기존의 컬렉터를 튜닝할 수 있다.

Chapter05 스트림 활용

필터링

스트림의 요소를 선택하는 방법 필터링

스트림 인터페이스가 지원하는 filter 메서드의 필터링 방법

• Predicate
  • 불린을 반환하는 함수를 인수로 받아서 필터링할 수 있다.
    • stream().filter(Dish::isVegetarian)
    • stream().filter(menu.price > 1000)
• 고유 요소 - distinct()
  • 고유 여부는 스트림에서 만든 객체의 hashCode, equals로 결정된다.

슬라이싱

스트림의 요소를 선택하거나 스킵하는 스트림

• Predicate - java9
  • takeWhile() - false가 등장하는 시점 직전까지의 데이터를 슬라이싱
  • dropWhile() - false 요소를 발견한 값 이후 슬라이싱
• 스트림 축소
  • .limit(n) - 발견하는 요소의 개수 발견 시 종료 → 정렬되지 않은 값에도 사용하기 용이함
• 요소 건너뛰기
  • .skip(n) - 발견하는 n개의 요소 스킵

매핑

특정 객체에서 특정 데이터를 선택하는 작업

• 스트림의 각 요소에 함수 적용

    List<Menu> menu ...
  
    List<String> dishNames = menu.stream()
                                                            .map(Dish::getName)
                                                            .collect(toList());
    => Stream<Menu> -> .map(Dish::getName) -> Stream<String>

• 평면화

  • flatMap() → Stream의 객체를 감싸는 것이 아니라 객체 자체를 반환하도록 한다.

    words.stream()
          .map(word -> word.split(""))//각 단어를 개별 문자를 포함하는 배열로 변환
                                                                  //Stream<String[]> or Stream<Stream<String>>
          .map(Arrays::stream) //String[]배열을 stream으로 감싸기
          .distinct()
          .collect(toList());
          //List<Stream<String>> 반환 -> 실패
    
    words.stream()
          .map(word -> word.split(""))
          .flatMap(Arrays::stream) // flatMap을 통해 만들어진 Stream<Stream<String>>을
                                                          //Stream<String>으로 평면화
          .distinct()
          .collect(toList());

flatMap은 각 배열을 스트림이 아니라 스트림의 콘텐츠로 매핑한다.(스트림의 언박싱 개념으로 이해)

검색

• 특정 속성이 데이터 집합에 있는지 여부를 검색하는 데이터 처리 기법 반환값은 Boolean

  • allMatch - 모두만족
  • anyMatch - 하나라도만족
  • noneMatch - 모두만족x
  • findFirst
  • findAny

• 쇼트서킷

  limit, allMatch, noneMatch, findFirst, findAny등의 Stream연산은 스트림의 모든 요소를 처리하지 않고도 결과 반환이 가능하다. 이러한 연산들을 쇼트서킷 연산이라고 부른다.

요소 검색

findAny 메서드는 현재 스트림에 있는 임의의 요소를 반환한다.

Dish dish = menu.stream()
        .filter(Dish::isVegetarian)
        .findAny();
 -> 컴파일 에러 (형태 불일치 findAny() -> Optional<Dish> 반환)

쇼트서킷을 통해 결과를 바로 받았지만, 이번에는 Optional이라는 개념이 나온다.

Optional이란?

만약 List

int sum = 0;
for(int x : numbers){
        sum += x;
}

->

int sum = numbers.stream()
                                .reduce(0, (a, b) -> a + b);

List<Dish> menu = Dish.menu;
        //1, 2, 3, 4
    List<String> names = menu.stream()
            .filter(dish -> {
              System.out.println("filtering:" + dish.getName());
              return dish.getCalories() > 300;
            })
            .map(dish -> {
              System.out.println("mapping:" + dish.getName());
              return dish.getName();
            })
            .sorted()
            .limit(3)
            .collect(Collectors.toList());
    System.out.println(names);

백준 2805번 나무 자르기
https://www.acmicpc.net/problem/2805

접근 방식

나무 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);

    }
}

후기

전형적인 이분탐색 문제 조금만 익숙해진다면 쉬운 이분탐색은 금방 풀 수 있을 것 같다.

백준 16401 과자 나눠주기

https://www.acmicpc.net/problem/16401

접근 방식

길이를 기준으로 이분탐색, 과자의 개수에 따라서 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);

    }
}

후기

이분탐색임을 알고 시작했는데, 아직 익숙하지 않아서 접근이 어려웠다.

백준 29812 아니 이게 왜 안돼

https://www.acmicpc.net/problem/29812

접근 방식

문자열 자체를 입력받은 후 문자열의 위치를 저장하는 Queue에 담았다.

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를 통해 계속 값을 더해줘서 그럴 것 같았다.