https://school.programmers.co.kr/learn/courses/30/lessons/131123

p131123 Level.3 GROUP BY

내가 시도한 방식

SELECT FOOD_TYPE, REST_ID, REST_NAME, MAX(FAVORITES)
FROM REST_INFO
GROUP BY FOOD_TYPE
ORDER BY FOOD_TYPE DESC;

정답

SELECT FOOD_TYPE, REST_ID, REST_NAME, FAVORITES
FROM REST_INFO
WHERE (FOOD_TYPE, FAVORITES) IN 
       (SELECT FOOD_TYPE, MAX(FAVORITES)
        FROM REST_INFO
        GROUP BY FOOD_TYPE)
ORDER BY FOOD_TYPE DESC

서브쿼리를 넣어야 하는 이유 : 두 컬럼의 조건이 일치해야 한다

처음 넣었던 MAX함수만으로 뽑게되면 식당 명과 일치하지 않게 되는 문제가 발생한다.

애플리케이션 수준 보안을 지원하는 스프링 시큐리티

스프링 시큐리티는 인프라적으로 가장 최상층에 위치한 애플리케이션 수준 보안을 구현한다

웹 애플리케이션의 일반적인 보안 취약성

• 인증 취약성
• 세션 고정
• XSS(교차 사이트 스크립팅)
• CSRF(사이트 간 요청 위조)
• 주입
• 기밀 데이터 노출
• 메서드 접근 제어 부족
• 알려진 취약성이 있는 종속성 이용

인증과 권한 부여의 취약성

• 인증(Authentication)
  • 애플리케이션을 이용하려는 사람을 식별하는 프로세스
  • 사용자의 ID를 확인하고 나면 권한을 부여하는 프로세스가 시작
• 권한 부여(Authorization)
  • 인증된 호출자가 특정 기능과 데이터에 대한 이용 권리가 있는지 확인하는 프로세스
  • ex) 대부분의 인증된 사용자는 본인의 계좌에서만 이체가 가능하다
• 세션 고정(Session fixation)
  • 웹 애플리케이션의 더 구체적이고 심각한 약점
  • 이미 생성된 세션 ID를 재이용해 유효한 사용자를 가장할 수 있다.
  • 취약성 발생이유 : 인증 프로세스 중 고유한 세션ID를 할장하지 않아 기존 세션ID가 재사용될 가능성이 있을 때 발생
  • 공격방식 : 세션ID가 URL에 들어있는 방식으로 세션이 구현되어있을 때 악성 링크를 클릭하도록 유인할 수 있다. 이 때 클릭했을 때 세션 ID가 탈취된다.
    세션 값을 쿠키에 저장하는 경우 피해자의 브라우저가 스크립트를 실행하도록 할 수도 있다.
• XSS(교차 사이트 스크립팅, Cross Site Scripting)
  • 클라이언트 쪽 스크립트를 주입해 다른 사용자가 이를 실행하도록 한다.
  • 소독 하는 과정을 통해 해결
  • 이 취약성으로 인해 발생되는 문제 : 계정 가장(세션 고정과 결합), DDOS

  • 

• CSRF(사이트 간 요청 위조, Cross-Site Request Forger)
  • 서버가 요청의 출처를 확인하지 않을 때 발생하는 문제(모든 곳에서 요청이 실행될 수 있음)
  • 일반적으로 공격자는 CSRF를 이용해 시스템의 데이터를 변경하는 동작을 실행
• 웹 애플리케이션의 주입(Injection) 취약성 이해
  • 주입 공격은 광범위한 공격 방식.
  • 공격자는 시스템에 특정 데이터를 주입하는 취약성을 이용
  • 공격의 목표 : 시스템의 데이터 변경, 삭제, 무단 이용을 유발
  • 주입 공격의 유형 : XSS Injection, SQL Injection, XPath Injection, OS Command Injection, LDAP Injection 등
• 민감한 데이터의 노출 처리하기
  • 공개정보가 아닌 것은 절대 로그에 기록하지 말아야 한다
  • 로그에 기록하지 말아야 하는 예시
    • [오류] 요청의 서명이 잘못되었습니다. 사용할 올바른 키는 X입니다.
    • [경고] 사용자 이름 X와 암호 Y를 이용하여 로그인하지 못했습니다.
    • [정보] 사용자 X가 올바른 암호 Y를 이용하여 로그인했습니다.
  • 애플리케이션에 예외가 발생했을 때 서버가 클라이언트에 반환하는 정보를 주의

  • 

  • 로그인의 예시
    • 사용자의 이름이 올바르지 않음, 사용자의 암호가 올바르지 않음
      보다 사용자 이름 또는 암호가 올바르지 않음을 통해 처리하는 것이 정보를 제공하지 않기에 더 바람직함
• 메서드 접근 제어 부족
  • 컨트롤러 단에서 구성했을 때 나중에 다른 컨트롤러에서 레포지토리 참조시 권한부여가 제대로 안될 수도 있다.

  • 

• 알려진 취약성이 있는 종속성 이용
  • 개발하는 애플리케이션이 아닌 기능을 만들기 위해 이용하는 라이브러리나 프레임워크 같은 종속성에 취약성이 있을 수 있다.
  • 메이븐 또는 그레이들 구성에 플러그인을 추가하면 정적 분석을 수행할 수 있음

OAuth 2 흐름 이해

인증 권한 부여 방식

• 사용자가 애플리케이션접근 시 백엔드 리소스 호출
• 권한 부여 서버를 호출해서 토큰을 획득, 자격증명, 갱신 토큰으로 토큰 획득
• 자격 증명, 갱신 토큰이 올바를 때 새로운 액세스 토큰을 클라이언트로 반환
• 리소스 호출 시 서버에 요청할 때 헤더에 액세스 토큰을 담아 서비스 이용

토큰 형태로 애플리케이션이 구현되었을 때 이점

• 클라이언트는 사용자 자격 증명을 저장할 필요 없이 액세스 토큰과 갱신 토큰만 저장하면 된다.
• 애플리케이션은 사용자 자격 증명을 노출하지 않는다.
• 토큰을 가로챘을 때 사용자 자격 토큰을 실격시킬 수 있다.
• 토큰을 사용했을 때는 제삼자가 사용자를 가장하지 않고도 사용자 대신 리소스에 접근할 수 있다. 토큰의 수명은 짧기에 취약성을 악용할 기한이 제한된다.

API 키, 암호화 서명, IP 검증을 이용해 요청 보안

교환되는 메시지를 아무도 변경하지 못하게 하기 위해 백엔드 구성요소간 보안을 거는 방식이 있다.

• 요청 및 응답 헤더에 정적 키 이용
• 암호화 서명으로 요청 및 응답 서명
• IP 주소에 검증 적용

통신의 신뢰성을 테스트하는 제일 좋은 방법은 암호화 서명을 이용하는 것

이 책에서 배울 내용

스프링 시큐리티를 배우는 실용적 접근법 소개

• 스프링 시큐리티의 아키텍처와 기본 구성 요소 및 이를 이용해 애플리케이션을 보호하는 방법
• OAuth 2 및 OpenID Connect 흐름과 시큐리티로 인증과 권한 부여를 구현하는 방법
• 애플리케이션의 다양한 계층에서 스프링 시큐리티로 보안을 구현하는 방법
• 다양한 구성 스타일과 프로젝트에 맞는 모범 사례
• 리액티브 애플리케이션에 스프링 시큐리티 이용
• 보안 구현 테스트

요약

• 스프링 시큐리티는 스프링 애플리케이션을 보호하기 위한 가장 인기 있는 선택이며 다양한 스타일과 아키텍처에 적용할 수 있는 갖가지 대안을 제공한다
• 시스템의 계층별로 보안을 적용해야 하며 계층별로 다른 관행을 이용해야 한다.
• 보안은 소프트웨어 프로젝트를 시작할 때부터 고려해야 하는 공통 관심사다
• 일반적으로 취약성을 예방하는 투자 비용보다 공격의 대가가 훨씬 크다.
• 오픈 웹 애플리케이션 보안 프로젝트(OWASP)는 취약성과 보안 관련 사항을 참고할 수 있는 훌륭한 장소다.
• 종종 아주 작은 실수 때문에 큰 피해가 발생한다.( 로그나 오류 메시지에 민감한 데이터 노출)

Chapter01 객체, 설계

step01. 구현

• 수동적이지 않은 객체
  • 객체의 메서드가 모두 열려있음 - public
  • 하나의 객체(Theater)가 모든 것을 조종함 - Processing(절차지향적)
• 변경에 취약한 코드
  • 요구사항이 변경 될 가능성
  • 구현된 클래스가 다른 클래스에 의존되어 구현된다.
  • 결합도(coupling)가 높음

public class Theater {
    private TicketSeller ticketSeller;

    public Theater(TicketSeller ticketSeller) {
        this.ticketSeller = ticketSeller;
    }

public void enter(Audience audience) {
        if (audience.getBag().hasInvitation()) {
            Ticket ticket = ticketSeller.getTicketOffice().getTicket();
            audience.getBag().setTicket(ticket);
        } else {
            Ticket ticket = ticketSeller.getTicketOffice().getTicket();
            audience.getBag().minusAmount(ticket.getFee());
            ticketSeller.getTicketOffice().plusAmount(ticket.getFee());
            audience.getBag().setTicket(ticket);
        }
    }
}

Step02. 설계 개선

• 자율적인 존재로 만들기
  • 기존 : 티켓 판매를 티켓 판매원이 아닌 Theater가 담당함
  • 변경 : 티켓 판매 로직을 티켓 판매원에게 양도
  • TicketSeller{ ... public void sellTo(Audience audience){ if(audienct.getBag().hasInvitation()){ Ticket ticket = ticketOffice.getTicket(); audience.getBag().setTicket(ticket); }else{ Ticket ticket = ticketOffice.getTicket(); audience.getBag().minusAmount(ticket.getFee()); ticketOffice.plusAmount(ticket.getFee90); audience.getBag().setTicket(ticket); } } ... } -> public class Theater { ... public void enter(Audience audience){ ticketSeller.sellTo(audience); } ... }
• 기존 : bag을 getter로 불러옴
• 변경 : bag을 private화 + getter삭제 + 공용 인터페이스인 buy()를 bag에 선언
• public class Audience{ public Bag bag; -> private Bag bag; public Bag getBag() { return bag; } -> public Long buy(Ticket ticket){ if( bag.hasInvitation()) { bag.setTicket(ticket); return 0L; } else { bag.setTicket(ticket); bag.minusAmount(ticket.getFee()); return ticket.getFee(); } }
• 변화점 : 각 객체들이 맡은 책임에 맞게 일을 행하도록 구현되었다.
• Theater의 경우를 예로 들었을 때 객체는 다른 객체에게 이 일을 행해달라고 전달했을 뿐이다.

캡슐화와 응집도

• 객체지향의 핵심은 객체 내부의 상태를 캡슐화하고 객체 간에 오직 공용 인터페이스(메시지)를 통해서만 상호작용하도록 만드는 것
• 객체가 밀접하게 연관된 작업만을 수행하고 연관성이 없는 작업은 다른 객체에게 위임하는 것이 응집도를 높이는 방법이다.
• 자신의 데이터를 책임지며 자신의 데이터를 가공하는 것이 객체의 응집도를 높이는 핵심

절차지향과 객체지향

• 절차적 프로그래밍
  Step01에서는 Theater가 절차지향적인 코드였으며, Process역할을 했었다. 이렇게 Step01의 Theater처럼 별도 모듈에 위치시키는 방식
• 객체지향 프로그래밍
  Step02에서는 프로세스가 각 객체 안에서 동작하도록 구성했다. ex)class Audience
• 책임의 이동(shift of responsibility)
  두 방식의 근본적인 차이는 기능을 처리할 때 Theater가 직접 처리를 하는 방식과, Theater가 말을하면 Audience와 TicketSeller가 스스로 처리를 하는 방식으로 구분을 할 수 있다.
  • 책임 집중 : Theater
  • 책임 분산 : buy → Audience, SellTo → TicketSeller

Step03. 추가 개선

TicketOffice

• 기존 : getTicket, getFee를 통해 티켓 자체를 Office에서 꺼내옴
• 변경 : sellTicketTo를 통해 기존의 티켓을 꺼내오는 방식 변경
• class TicketOffice{ ... public Ticket getTicket(){ ... } public void plusAmount(){ ... } ... } -> class TicketOffice{ ... public void sellTicketTo(Audience audience){ plusAmount(audience.buy(getTicket())); } private Ticket getTicket(){ ... } private void plusAmount(){ ... } ... } public TicketOffice getTicketOffice() { return ticketOffice; } -> public class TicketSeller{ public void sellTo(Audience audience){ ticketOffice.sellTicketTo(audience); } }
• 인터페이스에만 의존하게하는 형태로 변경됨
• but TicketSeller는 audience를 넘겨주며 서로 의존하게 만듦

트레이드오프

• 인터페이스에만 의존하는 Audience결합도가 중요한지, audience를 넘겨주며 의존성이 생겨난 것이 더 좋을지 개발자는 트레이드 오프를 해야 할 순간이 온다.
• 두가지 이슈를 통해 (책에서의)개발팀은 TicketOffice의 자율성을 지켜 의존성 제거를 택했다.

의인화

Theater, Bag, TicketOffice는 실세계에서 자율적인 존재가 아니다. 하지만 객체지향 패러다임에서는 생물과 동일하게 객체로 다뤘다. 이렇게 모든 객체는 능동적이고 자율적인 존재로 바뀌도록 설계하는 원칙을 의인화라고 부른다

설계

설계란 코드를 배치하는 것이다 - Metz12 -

• 요구사항은 항상 변경된다. → 코드는 항상 변경된다.
• 설계는 코드를 잘 배치하는 것 → 변경될 때 코드의 변경을 최소화하는 것
• 코드의 변경을 최소화하려면 → 객체 사이의 의존성을 적절하게 관리하는 것

EnumType을 엔티티 컬럼으로 생성할 때 반드시 @Enumerated(EnumType.STRING)을 사용해야 한다.

• 이넘 타입을 그대로 저장하게되면 ordinal() 형태로 저장된다.
• ordinal 형태로 저장하면 데이터는 조금 아낄 수 있다. but 혹시나 나중에 추가될 enum타입이 생긴다면, 0, 1, 2, 등 숫자로 파악해야 하므로 타입 데이터가 꼬이게 된다.
• 때문에 반드시 확실한 매핑을 할 수 있는 @Enumerated(EnumType.STRING) 스트링 형태로 컬럼을 생성하자

Chapter07 병렬 데이터 처리와 성능

자바의 병렬

자바 7 이전의 버전에서는 병렬의 처리가 어려웠다.
분할을 위한 스레드 할당 → 동기화 추가 → 결과 합치기의 과정을 통해 병렬 처리가 실행되는데, 각 병렬처리를 한 후에 스레드를 합칠 때 동기화를 적절히 이뤄줘야 교착 상태를 피할 수 있었다.
7버전 부터 지원하기 시작한 Fork/Join 프레임워크를 활용하면 해당 문제를 쉽고 효율적으로 해결할 수 있다. 이 Fork/Join 프레임워크를 활용한 스트림 API와 병렬 처리에 대해서 배워보자.

병렬 스트림

• 각각의 스레드에서 처리할 수 있도록 스트림 요소를 여러 청크로 분할한 스트림
• 멀티코어 프로세서가 각각의 청크를 처리하도록 한다
• Collections.parallelStream() or Arrays.stream().parallel()
  • Pipeline에있는 parallel 상태에 true가 저장된다.
  • 이후 파이프라인 처리할 때 처리할 때 parallel 체크를 통해 해결한다.
• 병렬 처리를 고려할 때는 성능 벤치마킹을 하는 것을 권장
• 성능 최적화
  • 기본형(primitive) 타입의 경우 기본형 특화 스트림 권장 - 오토박싱의 이유
  • 일반적으로 순차적인 처리가 필요한 스트림의 경우 병렬 비용이 더욱 비싸 느릴 가능성이 높음
  • 순차 처리가 필요없는 경우 findAny같은 순서에 상관 없는 쇼트 서킷, unordered 같은 메서드 사용
  • 하나의 요소를 처리하는 데 드는 비용이 비싸다면 고려
  • 스트림 자료구조의 특성을 확인 ex) LinkedList vs ArrayList 일반적으로 좋음
  • 병합 과정의 비용을 생각해야 한다

    | 소스 | 분해성 |
    | --- | --- |
    | ArrayList | Excellent |
    | LinkedList | Bad |
    | IntStream.range | Excellent |
    | Stream.iterate | Bad |
    | HashSet | Good |
    | TreeSet | Good |
    | Stream.generate | iterate보단 낫다 |

parallel처리 관련 이미지

포크/조인 프레임워크

• 병렬 작업할 때 사용

• 재귀적으로 큰 작업을 작은 작업으로 분할한 후 서브태스크의 결과를 합쳐서 전체 결과를 만듦

• 스레드 풀(ForkJoinPool)의 작업자 스레드에 분산 할당하는 ExecutorService

  • ExecutorService를 왜 언급하는가?

    RecursiveTask를 실제로 활용했을 때 해당 추상 클래스의 부모인 ForkJoinTask에서 ForkJoinPool을 활용해서 실제 활용하고있기 때문

    RecursiveTask → ForkJoinTask에서 사용하는 ForkJoinPool → ExcutorService

    

    

• 분할 정복(divide-and-conquer) 알고리즘의 병렬화

• compute() 메서드 오버라이딩 해서 구현

• 병렬처리 시 주의점

  • join 호출은 두 서브태스크가 모두 시작된 다음에 해야한다.
  • ForkJoinPool의 invoke메서드는 병렬 계산 시작하는 시점에서 한번만 사용
  • 한쪽은 fork() 한쪽은 compute() ⇒ 같은 스레드 재사용 피하기 위함
  • 디버깅이 어렵다 ⇒ 스택이 아닌 다른 스레드 이기 때문
  • 병렬 처리가 무조건 빠르지 않다.

• 작업 훔치기(work stealing) 특성을 갖고있음

• ForkJoin을 활용한 RecursiveTask 예시

import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;
import java.util.stream.LongStream;

public class ForkJoinSumCalculator extends RecursiveTask<Long> {

    //THRESHOLD 이상의 값 까지만 분해
  public static final long THRESHOLD = 10_000;

  private final long[] numbers;
  private final int start;
  private final int end;

  public ForkJoinSumCalculator(long[] numbers) {
    this(numbers, 0, numbers.length);
  }

  private ForkJoinSumCalculator(long[] numbers, int start, int end) {
    this.numbers = numbers;
    this.start = start;
    this.end = end;
  }

  @Override
  protected Long compute() {
    int length = end - start; //해당 태스크에서 더할 배열의 길이
    if (length <= THRESHOLD) {
      return computeSequentially();
    }
        //각 태스크 분리 left, right
    ForkJoinSumCalculator leftTask =
        new ForkJoinSumCalculator(numbers, start, start + length / 2);
        //생성한 태스크 비동기 실행
    leftTask.fork();
    ForkJoinSumCalculator rightTask =
        new ForkJoinSumCalculator(numbers, start + length / 2, end);
        //두번째 태스크 동기 실행
    Long rightResult = rightTask.compute();
        //비동기 실행했던 left의 결과를 읽거나 처리완료 후 읽기까지 대기
    Long leftResult = leftTask.join();
    return leftResult + rightResult;
  }

    //가장 작은 단위일 때 작은 단위로 쪼갠 태스크의 결과를 계산
  private long computeSequentially() {
    long sum = 0;
    for (int i = start; i < end; i++) {
      sum += numbers[i];
    }
    return sum;
  }

    public static long forkJoinSum(long n) {
    long[] numbers = LongStream.rangeClosed(1, n).toArray();
    ForkJoinTask<Long> task = new ForkJoinSumCalculator(numbers);
    return FORK_JOIN_POOL.invoke(task);
  }
}

//호출 방법
ForkJoinSumCalculator.forkJoinSum(long n));

Spliterator 인터페이스

• 구성 요소
  • booleaen tryAdvance(Consumer<? super T> action)
    • 요소를 하나씩 순차적으로 돌며 요소가 남아있는지 확인
  • Spliterator trySplit()
    • 일부 요소를 분할해서 새로운 Spliterator 생성
  • long estimateSize()
    • 탐색해야 할 요소 수 정보 제공(RecursiveTask의 THRESHOLD 역할로 보임)
  • int characteristics()
    • 다양한 특성 집합을 포함(ORDERED, DISTINCT 그 외 다수)

7장을 마치며

• 내부 반복을 통해 명시적으로 스트림 병렬처리
• 병렬처리가 무조건 빠르지 않음 특성과 병렬처리 후의 결과 등을 잘 확인하여 고려할 것
• 병렬 처리에는 포크/조인 프레임워크를 활용한다
• Spliterator를 통해 병렬 처리를 직접 정의할 수 있다.

백준 싫은데요

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