[워밍업클럽4기-CS] 2주차 미션 - 자료구조와 알고리즘

[워밍업클럽4기-CS] 2주차 미션 - 자료구조와 알고리즘

avraskio 4개월 전 
package DataStructure.cpu;

public class BinaryTree<T> {
    private T data;
    private BinaryTree<T> leftTree;
    private BinaryTree<T> rightTree;
    private BinaryTree<T> parentTree;

    public BinaryTree(T data) {
        this.data = data;
        this.leftTree = null;
        this.rightTree = null;
        this.parentTree = null;
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BinaryTree<T> getLeftSubTree() {
        return this.leftTree;
    }

    public void setLeftSubTree(BinaryTree<T> leftTree) {
        this.leftTree = leftTree;
    }

    public BinaryTree<T> getRightSubTree() {
        return this.rightTree;
    }

    public void setRightSubTree(BinaryTree<T> rightTree) {
        this.rightTree = rightTree;
    }

    public BinaryTree<T> removeLeftSubTree() {
        BinaryTree<T> deletingNode = this.leftTree;
        this.setLeftSubTree(null);
        return deletingNode;
    }

    public BinaryTree<T> removeRightSubTree() {
        BinaryTree<T> deletingNode = this.rightTree;
        this.setRightSubTree(null);
        return deletingNode;
    }

    // 전위순회
    public void preOrderTraversal() {
        System.out.print(this.data + " ");
        if (this.leftTree != null) {
            this.leftTree.preOrderTraversal();
        }
        if (this.rightTree != null) {
            this.rightTree.preOrderTraversal();
        }
    }

    // 중위순회
    public void inOrderTraversal() {
        if (this.leftTree != null) {
            this.leftTree.inOrderTraversal();
        }
        System.out.print(this.data + " ");
        if (this.rightTree != null) {
            this.rightTree.inOrderTraversal();
        }
    }

    // 후위순회
    public void postOrderTraversal() {
        if (this.leftTree != null) {
            this.leftTree.postOrderTraversal();
        }
        if (this.rightTree != null) {
            this.rightTree.postOrderTraversal();
        }
        System.out.print(this.data + " ");
    }

    public BinaryTree<T> getParentTree() {
        return this.parentTree;
    }

    public void setParentTree(BinaryTree<T> parentTree) {
        this.parentTree = parentTree;
    }

    public static void main(String[] args) {
        BinaryTree<Integer> tree1 = new BinaryTree<>(1);
        BinaryTree<Integer> tree2 = new BinaryTree<>(2);
        BinaryTree<Integer> tree3 = new BinaryTree<>(3);
        BinaryTree<Integer> tree4 = new BinaryTree<>(4);
        BinaryTree<Integer> tree5 = new BinaryTree<>(5);
        BinaryTree<Integer> tree6 = new BinaryTree<>(6);
        BinaryTree<Integer> tree7 = new BinaryTree<>(7);

        tree1.setLeftSubTree(tree2);
        tree1.setRightSubTree(tree3);
        tree2.setLeftSubTree(tree4);
        tree2.setRightSubTree(tree5);
        tree3.setLeftSubTree(tree6);
        tree3.setRightSubTree(tree7);

        tree1.preOrderTraversal();
        System.out.println();
        tree1.inOrderTraversal();
        System.out.println();
        tree1.postOrderTraversal();
    }
}
package DataStructure.cpu;

public class Heap<T extends Comparable<T>> {
    public BinaryTree<T> root;
    public BinaryTree<T> lastInsertedNode;

    public Heap() {
        this.root = null;
        this.lastInsertedNode = null;
    }

    public void insert(T data) {
        if (this.lastInsertedNode == null) {
            this.lastInsertedNode = new BinaryTree<>(data);
            this.root = this.lastInsertedNode;
            return;
        }

        BinaryTree<T> insertingParent = this.getInsertingParent();
        BinaryTree<T> newNode = new BinaryTree<>(data);

        if (insertingParent.getLeftSubTree() == null) {
            insertingParent.setLeftSubTree(newNode);
        } else if (insertingParent.getRightSubTree() == null) {
            insertingParent.setRightSubTree(newNode);
        }
        newNode.setParentTree(insertingParent);
        this.lastInsertedNode = newNode;

        while (newNode.getParentTree() != null) {
            if (this.isBigPriority(newNode.getData(), newNode.getParentTree().getData())) {
                T tempData = newNode.getParentTree().getData();
                newNode.getParentTree().setData(newNode.getData());
                newNode.setData(tempData);
                newNode = newNode.getParentTree();
            } else {
                break;
            }
        }
    }

    private boolean isBigPriority(T first, T second) {
        return first.compareTo(second) < 0;
    }

    private BinaryTree<T> getInsertingParent() {
        if (this.lastInsertedNode.getParentTree() == null) { // 1번 케이스
            return this.lastInsertedNode;
        } else {
            if (this.lastInsertedNode == this.lastInsertedNode.getParentTree().getLeftSubTree()) { // 2번 케이스
                return this.lastInsertedNode.getParentTree();
            } else { // 3번 케이스
                BinaryTree<T> current = this.lastInsertedNode;
                BinaryTree<T> firstRightSibling = null;

                while (current.getParentTree().getParentTree() != null) {
                    current = current.getParentTree();

                    firstRightSibling = this.getRightSibling(current);
                    if (firstRightSibling != null) {
                        break;
                    }
                }

                if (firstRightSibling != null) {
                    while (firstRightSibling.getLeftSubTree() != null) {
                        firstRightSibling = firstRightSibling.getLeftSubTree();
                    }
                    return firstRightSibling;
                } else {
                    current = this.root;
                    while(current.getLeftSubTree() != null) {
                        current = current.getLeftSubTree();
                    }
                    return current;
                }
            }
        }
    }

    private BinaryTree<T> getRightSibling(BinaryTree<T> node) {
        if (node.getParentTree().getRightSubTree() != node) {
            return node.getParentTree().getRightSubTree();
        }
        return null;
    }

    private BinaryTree<T> getLeftSibling(BinaryTree<T> node) {
        if (node.getParentTree().getLeftSubTree() != node) {
            return node.getParentTree().getLeftSubTree();
        }
        return null;
    }

    public BinaryTree<T> remove() {
        BinaryTree<T> deletedNode;

        if (this.lastInsertedNode == this.root) {
            deletedNode = this.root;
            this.root = null;
            this.lastInsertedNode = null;
            return deletedNode;
        }

        BinaryTree<T> prevLastInsertedNode = this.getNewLastInsertedNode();
        T tempData = this.root.getData();
        this.root.setData(this.lastInsertedNode.getData());
        this.lastInsertedNode.setData(tempData);

        if (this.lastInsertedNode.getParentTree().getLeftSubTree() == this.lastInsertedNode) {
            this.lastInsertedNode.getParentTree().setLeftSubTree(null);
        } else {
            this.lastInsertedNode.getParentTree().setRightSubTree(null);
        }
        this.lastInsertedNode.setParentTree(null);
        deletedNode = this.lastInsertedNode;
        this.lastInsertedNode = prevLastInsertedNode;

        BinaryTree<T> current = this.root;
        do {
            BinaryTree<T> higherChild = this.getHigherPriorityChild(current.getLeftSubTree(),
                current.getRightSubTree());
            if (higherChild == null) {
                break;
            } else if (!this.isBigPriority(current.getData(), higherChild.getData())) {
                T tempData2 = current.getData();
                current.setData(higherChild.getData());
                higherChild.setData(tempData2);
                current = higherChild;
            } else {
                break;
            }
        } while (current.getLeftSubTree() != null || current.getRightSubTree() != null);
        return deletedNode;
    }

    private BinaryTree<T> getHigherPriorityChild(BinaryTree<T> left, BinaryTree<T> right) {
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else if (this.isBigPriority(left.getData(), right.getData())) {
            return left;
        } else {
            return right;
        }
    }

    private BinaryTree<T> getNewLastInsertedNode() {
        BinaryTree<T> prevLastInsertedNode;
        if (this.lastInsertedNode == this.lastInsertedNode.getParentTree().getLeftSubTree()) { // 1 케이스
            BinaryTree<T> current = this.lastInsertedNode;
            BinaryTree<T> firstLeftSibling = null;
            while (current.getParentTree().getParentTree() != null) {
                current = current.getParentTree();
                firstLeftSibling = this.getLeftSibling(current);
                if (firstLeftSibling != null) {
                    break;
                }
            }

            if (firstLeftSibling != null) { // a 케이스
                while (firstLeftSibling.getRightSubTree() != null) {
                    firstLeftSibling = firstLeftSibling.getRightSubTree();
                }
                prevLastInsertedNode = firstLeftSibling;
            } else { // b 케이스
                current = this.root;
                while (current.getRightSubTree() != null) {
                    current = current.getRightSubTree();
                }
                prevLastInsertedNode = current;
            }
        } else { // 2 케이스
            prevLastInsertedNode = this.lastInsertedNode.getParentTree().getLeftSubTree();
        }
        return prevLastInsertedNode;
    }

}
package DataStructure.cpu;

public class CpuScheduler<T extends Comparable<T>> {
    private Heap<T> heap;

    public CpuScheduler() {
        this.heap = new Heap<>();
    }

    public void scheduleTask(T task) {
        this.heap.insert(task);
    }

    public T executeNextTask() {
        return this.heap.remove().getData();
    }
}
package DataStructure.cpu;

public record Process(
    String name,
    int cpuReturnCount,
    int executionCount
) implements Comparable<Process> {

    @Override
    public int compareTo(Process o) {
        if(this.executionCount == o.executionCount) {
            return Integer.compare(o.cpuReturnCount, this.cpuReturnCount);
        }
        return Integer.compare(this.executionCount, o.executionCount);
    }
}
public class Main {

    public static void main(String[] args) {
        CpuScheduler<Process> cpuScheduler = new CpuScheduler<>();

        cpuScheduler.scheduleTask(new Process("수치계산프로그램", 4, 0));
        cpuScheduler.scheduleTask(new Process("뮤직플레이어", 11, 10));
        cpuScheduler.scheduleTask(new Process("웹브라우저", 27, 25));
        cpuScheduler.scheduleTask(new Process("터미널1", 34, 2));
        cpuScheduler.scheduleTask(new Process("터미널2", 93, 2));

        System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask());
        System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask());
        System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask());
        System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask());
        System.out.println("다음 실행할 프로세스: " + cpuScheduler.executeNextTask());
    }
}

========================= 터미널 =========================
다음 실행할 프로세스: Process[name=수치계산프로그램, cpuReturnCount=4, executionCount=0]
다음 실행할 프로세스: Process[name=터미널2, cpuReturnCount=93, executionCount=2]
다음 실행할 프로세스: Process[name=터미널1, cpuReturnCount=34, executionCount=2]
다음 실행할 프로세스: Process[name=뮤직플레이어, cpuReturnCount=11, executionCount=10]
다음 실행할 프로세스: Process[name=웹브라우저, cpuReturnCount=27, executionCount=25]

댓글을 작성해보세요.

채널톡 아이콘