## 과제 : 제네릭 이진 트리 구현

목표 : 제네릭을 사용하여 다양한 데이터 타입을 저장할 수 있는 이진 트리를 구현한다.

요구사항 : 다음 코드를 참고하여, 제네릭을 사용하여 다양한 데이터 타입을 저장할 수 있는 이진 트리를 구현한다.

public class MyBinaryTree {
    public static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    private Node root;

    public void insert(int value) {
        root = insert(root, value);
    }

    private Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.data) {
            node.left = insert(node.left, value);
        } else if (value > node.data) {
            node.right = insert(node.right, value);
        }

        return node;
    }

    public boolean contains(int value) {
        return contains(root, value);
    }

    private boolean contains(Node node, int value) {
        if (node == null) {
            return false;
        }

        if (value < node.data) {
            return contains(node.left, value);
        } else if (value > node.data) {
            return contains(node.right, value);
        } else {
            return true;
        }
    }

    public void delete(int value) {
        root = delete(root, value);
    }

    private Node delete(Node node, int value) {
        if (node == null) {
            return null;
        }

        if (value < node.data) {
            node.left = delete(node.left, value);
        } else if (value > node.data) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            node.data = findMin(node.right).data;
            node.right = delete(node.right, node.data);
        }

        return node;
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

### 과제를 수행하기 전에 Comparable 인터페이스에 대해서 알아보자

Comparable 인터페이스란?

- Comparable 인터페이스는 객체를 비교하는데 사용되는 인터페이스이다. 이를 통해 객체들을 정렬할 때 기준을 제공한다
- 객체들의 자연 순서를 정의하기 위해 사용된다.
- Comparable 인터페이스를 구현한 클래스의 인스턴스는 서로 비교가 가능하며, 이를 통해 정렬이나 순서를 관리하는 작업을 수행할 수 있다.
- Comparable 인터페이스는 같은 자료형의 다른 객체 하나를 인자로 받아와 비교하는 compareTo 함수를 사용한다.
- public int compareTo(T o);
- 현재 객체가 매개변수 객체보다 작을 경우: 음수 값을 반환.
- 현재 객체와 매개변수 객체가 같을 경우: 0을 반환.
- 현재 객체가 매개변수 객체보다 클 경우: 양수 값을 반환.

#### Comparable 인터페이스 구현 예

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age; // 나이를 기준으로 비교
    }
}

## 과제: 블랙잭 게임 구현

**목표: 콘솔 인터페이스에서 블랙잭 게임을 구현한다.**

블랙잭은 카드 게임으로, 플레이어와 딜러가 카드를 받아 21에 가까운 숫자를 만드는 게임이다.

플레이어와 딜러는 각각 2장의 카드를 받고, 플레이어는 카드를 더 받을지(‘Hit’) 그만 받을지(‘Stand’)를 선택할 수 있다.

플레이어는 카드를 더 받을 때마다 카드의 숫자를 합계하여 21에 가까워지도록 해야 하며, 21을 초과하면 패배한다.
이 때 `A`는 1 또는 11로 계산할 수 있으며, `J`, `Q`, `K`는 각각 10으로 계산한다.

딜러는 카드를 더 받을지 여부를 선택할 수 없으며, 딜러는 16 이하일 때는 무조건 카드를 더 받고, 17 이상일 때는 카드를 받지 않는다.

**요구사항:**

1. **게임 준비**
- 52장의 카드 덱을 생성하고 섞는다.
- 플레이어와 딜러에게 각각 2장의 카드를 나눠준다.
- 딜러의 첫 번째 카드만 공개하고, 두 번째 카드는 가린다.

2. **플레이어 턴**
- 플레이어의 카드 합계를 보여준다.
- 플레이어에게 'Hit' 또는 'Stand'를 입력받는다.
- 'Hit'를 선택하면 플레이어에게 한 장의 카드를 더 나눠준다.
- 'Stand'를 선택하면 플레이어의 턴이 종료된다.
- 플레이어의 카드 합계가 21을 초과하면 자동으로 'Bust'되어 게임에서 진다.

3. **딜러 턴**
- 딜러의 두 번째 카드를 공개한다.
- 딜러의 카드 합계가 16 이하이면 계속해서 카드를 받는다.
- 딜러의 카드 합계가 17 이상이면 'Stand'한다.

4. **게임 결과**
- 플레이어와 딜러의 카드 합계를 비교한다.
- 21에 가까운 쪽이 이기거나, 상대방이 'Bust'되면 이긴다.
- 비기면 무승부가 된다.
- 게임 결과를 출력한다.

5. **다시 플레이**
- 게임이 종료된 후, 플레이어에게 다시 플레이할지 여부를 묻는다.

## 과제 : 제네릭 이진 트리 구현 모범 답안

public class MyBinaryTree<T extends Comparable<T>> {
    public static class Node<T> {
        T data;
        Node<T> left;
        Node<T> right;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> root;

    public void insert(T value) {
        root = insert(root, value);
    }

    private Node<T> insert(Node<T> node, T value) {
        if (node == null) {
            return new Node<>(value);
        }

        int cmp = value.compareTo(node.data);
        if (cmp < 0) {
            node.left = insert(node.left, value);
        } else if (cmp > 0) {
            node.right = insert(node.right, value);
        }

        return node;
    }

    public boolean contains(T value) {
        return contains(root, value);
    }

    private boolean contains(Node<T> node, T value) {
        if (node == null) {
            return false;
        }

        int cmp = value.compareTo(node.data);
        if (cmp < 0) {
            return contains(node.left, value);
        } else if (cmp > 0) {
            return contains(node.right, value);
        } else {
            return true;
        }
    }

    public void delete(T value) {
        root = delete(root, value);
    }

    private Node<T> delete(Node<T> node, T value) {
        if (node == null) {
            return null;
        }

        int cmp = value.compareTo(node.data);
        if (cmp < 0) {
            node.left = delete(node.left, value);
        } else if (cmp > 0) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            node.data = findMin(node.right).data;
            node.right = delete(node.right, node.data);
        }

        return node;
    }

    private Node<T> findMin(Node<T> node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

## 과제 : 블랙잭 게임 구현 모범 답안

package test;

import java.util.*;

public class BlackjackGame {
    private static final int BLACKJACK = 21;
    private static final String[] SUITS = {"♥", "♦", "♣", "♠"};
    private static final String[] RANKS = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};

    private final static List<String> deck = new ArrayList<>();
    private final static List<String> playerHand = new ArrayList<>();
    private final static List<String> dealerHand = new ArrayList<>();
    private final static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        initializeDeck();
        playGame();
    }

    private static void initializeDeck() {
        for (String suit : SUITS) {
            for (String rank : RANKS) {
                deck.add(rank + suit);
            }
        }
        shuffle(deck);
    }

    public static void shuffle(List<String> list) {
        Random random = new Random();

        for (int i = list.size() - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);

            list.set(i, list.set(j, list.get(i)));
        }
    }

    private static void playGame() {
        do {
            playerHand.clear();
            dealerHand.clear();

            dealInitialCards();
            printGameState(true);

            playerTurn();

            if (!playerBusted()) {
                dealerTurn();
            }

            printFinalGameState();
            determineWinner();

        } while (playAgain());
    }

    private static void dealInitialCards() {
        playerHand.add(deck.remove(0));
        dealerHand.add(deck.remove(0));
        playerHand.add(deck.remove(0));
        dealerHand.add(deck.remove(0));
    }

    private static void printGameState(boolean hideSecondDealerCard) {
        System.out.println("플레이어 카드: " + playerHand);
        System.out.print("딜러 카드: " + dealerHand.get(0));
        if (hideSecondDealerCard) {
            System.out.println(" ?");
        } else {
            System.out.println(" " + dealerHand.get(1));
        }
    }

    private static void playerTurn() {
        while (true) {
            System.out.print("히트하시겠습니까? (y/n): ");
            String choice = scanner.nextLine().trim().toLowerCase();

            if (choice.equals("y")) {
                playerHand.add(deck.remove(0));
                printGameState(true);

                if (getHandValue(playerHand) > BLACKJACK) {
                    System.out.println("플레이어 버스트!");
                    return;
                }
            } else if (choice.equals("n")) {
                break;
            } else {
                System.out.println("올바른 입력이 아닙니다. 다시 입력해주세요.");
            }
        }
    }

    private static boolean playerBusted() {
        return getHandValue(playerHand) > BLACKJACK;
    }

    private static void dealerTurn() {
        System.out.println("딜러 턴 시작");
        printGameState(false);

        while (getHandValue(dealerHand) < 17) {
            dealerHand.add(deck.remove(0));
            System.out.println("딜러가 카드를 받았습니다.");
            printGameState(false);
        }

        if (getHandValue(dealerHand) > BLACKJACK) {
            System.out.println("딜러 버스트!");
        }
    }

    private static void printFinalGameState() {
        System.out.println("\n최종 게임 상태");
        System.out.println("플레이어 카드: " + playerHand + " (합계: " + getHandValue(playerHand) + ")");
        System.out.println("딜러 카드: " + dealerHand + " (합계: " + getHandValue(dealerHand) + ")");
    }

    private static void determineWinner() {
        int playerValue = getHandValue(playerHand);
        int dealerValue = getHandValue(dealerHand);

        if (playerBusted()) {
            System.out.println("플레이어 패배!");
        } else if (dealerValue > BLACKJACK) {
            System.out.println("플레이어 승리!");
        } else if (playerValue > dealerValue) {
            System.out.println("플레이어 승리!");
        } else if (playerValue < dealerValue) {
            System.out.println("플레이어 패배!");
        } else {
            System.out.println("무승부!");
        }
    }

    private static boolean playAgain() {
        System.out.print("\n다시 플레이하시겠습니까? (y/n): ");
        String choice = scanner.nextLine().trim().toLowerCase();
        return choice.equals("y");
    }

    private static int getHandValue(List<String> hand) {
        int value = 0;
        int aceCount = 0;

        for (String card : hand) {
            String rank = card.substring(0, card.length() - 1);
            if (rank.equals("A")) {
                aceCount++;
            } else if (rank.equals("J") || rank.equals("Q") || rank.equals("K")) {
                value += 10;
            } else {
                value += Integer.parseInt(rank);
            }
        }

        while (aceCount > 0) {
            if (value + 11 <= BLACKJACK) {
                value += 11;
            } else {
                value += 1;
            }
            aceCount--;
        }

        return value;
    }
}