[TIL] 2월 25일

yeon·2021년 2월 25일
BFSTIL스트림탐색알고리즘
0

미션5 고민한 부분

[yeon] 미션5: 보드에 위치 부여 및 점수계산 by kimnayeon0108 · Pull Request #154 · codesquad-members-2021/java-chess

Board 클래스

  • 세로줄에 있는 폰의 개수 구하기

getSameFileNum() : 같은 세로줄에 있는 폰의 개수

deletedSamePositionNum : 폰의 개수에서 중복된걸 뺀 값

pawn 에서 deletedSamePositionNum 을 빼고 두배를 하면 같은 세로줄에 있는 폰의 개수

너무 복잡한가.. 

public double getSameFileNum(double pawnNum, Piece.Color color) {
    Piece piece =
            color == Piece.Color.WHITE ? Piece.createWhitePawn() : Piece.createBlackPawn();
    String[] positions = getPosition(piece);
    long deletedSamePositionNum = Arrays.stream(positions)
              .map(x -> x.charAt(0))
              .distinct()
              .count();
    return (pawnNum - deletedSamePositionNum) * 2;
}

처음에 이렇게 했다가, positions 배열을 hashSet으로 바꿔주면 중복되는 요소가 사라지니깐 코드가 더 간결해질거같아서 hashSet으로 변경하고 컬렉션의 크기를 비교해주도록 코드 변경

public double getSameFileNum(double pawnNum, Piece.Color color) {
    Piece piece =
            color == Piece.Color.WHITE ? Piece.createWhitePawn() : Piece.createBlackPawn();
    String[] positions = getPosition(piece);
    Set<String> deletedSamePositions = new HashSet<>(Arrays.asList(positions));
    return (pawnNum - deletedSamePositions.size()) * 2
}

그래도 좀 복잡해보이지만 이게 제일 나은거같다

근데 보는 사람 입장에서는 갑자기 HashSet이 왜나왔지? 라는 생각이 들수도 있을거같다.
내일 다른분들 pr보고 어떻게 구현했는지 봐야겠다

  • 정렬하기 sortPiece()

보드에 있는 랭크 스트림으로 만들기

→ 랭크에 있는 기물 리스트들 flatMap으로 합치기

→ 타입 스트림으로 바꾸기

→ 점수 순서대로 정렬하기

  • Board 클래스가 너무 많은 일을 하는것 같다.
    요구사항에서 제안한대로 위치와 관련된 작업을 하는 클래스를 하나 더 생성하면 코드를 다시 수정하는 작업이 힘들거 같아서 일단 Board 에서 처리하도록 했다. 여기까지 구현하는것도 오래걸려서 빨리 pr보내고 싶었다...ㅠㅠ

  • 요구사항에 나와있는대로 createWhite(type)과 createBlack(type)메소드를 생성하고, 각각의 기물들의 팩토리메소드에서 이를 호출하도록 구현

    그런데 각각 기물을 생성하는 메소드가 굳이 필요한가? 기물생성시 createWhite()나 createBlack()을 써서 생성하면 안되나 라는 생각이 듦

    → 팩토리메소드의 특징상 메소드명에 기물도 포함되어야할거 같다는 생각도 든다.

AssertJ

아래 블로그 참고

AssertJ 소개

Maven 의존성 설정

<dependency>
	<groupId>org.assertj</groupId>
	<artifactId>assertj-core</artifactId>
	<!-- use 2.6.0 for Java 7 projects -->
  <version>3.6.2</version>
	<scope>test</scope>
</dependency>

Gradle 의존성 설정

  • Java 8
testCompile 'org.assertj:assertj-core:3.6.2'

AssertJ 메소드 임포트

import static org.assertj.core.api.Assertions.*;

메소드 (assertThat()에 연쇄적으로 사용)

  • isNotEmpty()
  • contains()
  • doseNotContain()
  • startsWith()
  • endsWith()
  • isEqualTo()
  • isPositive()
  • isGraterThan()
  • isLessThan()

자바의 정석 831p에 해당내용 있음

스트림 flatMap() 이해하기

스트림의 스트림을 스트림으로 변환

예시 : Stream<T[]>을 Stream으로 변환

내가 체스프로젝트에 flatMap적용한 코드

public List<Type> sortPiece(Color color) {
        return board.stream()
                .map(x -> x.getPieceList())
                .flatMap(List::stream)
                .filter(s -> s.getColor() == color)
                .map(x -> x.getType())
                .sorted(Comparator.comparing(Type::getDefaultPoint).reversed())
                .collect(Collectors.toList());
    }
  • board 리스트는 Rank 객체를 담고 있다. List< Rank > board
  • map으로 스트림의 요소들을 Rank에 있는 pieceList로 바꾼다. Stream<List< Piece >>
    • pieceList는 Piece 객체를 담고 있는 리스트
  • flatMap으로 Stream<List< Piece >>였던걸 Stream< Piece >로 바꿔준다.

언제 for loop대신 stream API를 사용하면 좋을까 (출처: 이노의 pr 중 리뷰어의 코멘트, 로치가 공유해주심)

다음과 같은 상황에서는 stream API의 사용이 적절합니다.

  • Iterable 객체에 담긴 요소를 일괄 변환할때
  • 요소들이 갖고 있는 상태값을 기반으로 합, 평균 등을 구할 때
  • 일정한 조건에 맞는 요소들의 갯수를 셀 때

for loop 외부에 index 나 count 같은 변수를 두고 하나씩 올려가는 것보다, 리스트를 직접 변환하고 걸러내서 결과값을 도출하는 것이 훨씬 안전하고 깔끔한 코드가 됩니다.

이코테 탐색알고리즘 DFS/BFS 파트

BFS

너비 우선 탐색

가장 가까운 노드부터 탐색

동작 방식

  1. 탐색 시작 노드를 큐에 넣고 방문처리
  2. 큐에서 노드를 꺼내고
  3. 꺼낸 노드의 인접 노드중 방문하지 않은 노드를 큐에 넣고 방문처리
  4. 2,3번 반복

BFS 예제

public class BFSExam {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    // BFS 함수 정의
    public static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드 방문처리
        visited[start] = true;
        // 큐가 빌때까지 반복
        while (!q.isEmpty()){
            int x = q.poll();
            System.out.print(x + " ");
            // 해당 원소와 연결되고 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++){
                int y = graph.get(x).get(i);
                if(!visited[y]){
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);

        graph.get(2).add(1);
        graph.get(2).add(7);

        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);

        graph.get(4).add(3);
        graph.get(4).add(5);

        graph.get(5).add(3);
        graph.get(5).add(4);

        graph.get(6).add(7);

        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);

        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
    }
}

DFS와 BFS 구현방법과 동작원리

DFS : 스택 자료구조로 동작, 재귀함수로 구현

BFS : 큐 자료구조, 큐를 이용해서 구현

코딩테스트에서 탐색 문제가 나오면 그래프형태로 표현하고 풀기

오늘 한일

  • 드디어 미션5를 완료하고 pr까지 보냈다. 어려웠던 미션이였는데 이제 막 공부한 스트림을 이용해서 구현해볼 기회가 많아서(?) 좋았다. 스트림을 잘 사용한건지는 모르겠지만 잘못된 부분은 리뷰어가 피드백을 주시지 않을까 싶다. 스트림을 사용하니깐 복잡한 작업들(스트림의 요소들을 변환시키고, 스트림을 합하는 작업들 등...)을 간단하게 구현할수 있어서 좋았다.
    • 언제 for 루프를 쓰고 스트림API를 쓸지를 생각하고 써야겠다.
  • flatMap()의 이해
  • 나중에 보고 참고할 수 있게 assertJ의 메소드들을 정리해놨다.
  • 탐색 알고리즘 BFS

Todo

(내일)

  • 자바의 정석 쓰레드 학습하고 오늘 수업한거랑 같이 정리
  • 탐색알고리즘 문제풀기
profile
yeon
이전 포스트

[TIL] 2월 23일

다음 포스트

[TIL] 2월 26일

0개의 댓글