[멀티캠퍼스] 풀스택 개발자 아카데미 (13) - Algorithm(2)

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

public void solution(List<Integer> list) {
    // 전체 드워프의 키 합
    int total = list.stream().mapToInt(Integer::intValue).sum();
    // 찾아야할 두 숫자의 합
    int target = total - 100;

    // 삭제할 (제외되어야 할) 드워프
    List<Integer> toRemove = new ArrayList<>();
    // 완전 탐색
    for (int i = 0; i < list.size(); i++) {
        for (int j = i + 1; j < list.size(); j++) {
            // 조건에 맞는 두 난쟁이는 찾으면, 리스트에 추가하고 탐색 종료
            if (list.get(i) + list.get(j) == target) {
                toRemove.add(list.get(i));
                toRemove.add(list.get(j));
                break;
            }
        }
        if (toRemove.size() == 2) {
            break;
        }
    }

    // 리스트에서 제거
    for (Integer integer : toRemove) {
        list.remove(integer);
    }
    // 정렬하기
    Collections.sort(list);
    // List는 Reference 타입이므로, 입력받은 list가 수정됨.
    // 즉, 다시 반환할 필요가 없음.
    // 원본 배열을 유지하려면, 배열을 복사하여 사용
}

// 트리구조의 Node를 나타내는 클래스
public class Node<E> {
    // 데이터
    private E data;
    // 좌측 자식 노드
    private Node<E> left;
    // 우측 자식 노드
    private Node<E> right;

    public Node(E data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    // Data Getter/Setter
    public E getData() { return data; }
    public void setData(E data) { this.data = data; }

    // 자식 노드 Getter/Setter
    public Node<E> getLeft() { return left; }
    public Node<E> getRight() { return right; }
    public void setLeft(Node<E> left) { this.left = left; }
    public void setRight(Node<E> right) { this.right = right; }

    // 문자열 출력 시 사용
    @Override
    public String toString() { return data.toString(); }
}

// 순회하고, 방문한 순서를 LinkedList로 반환
public List<E> preorderDfs() {
    // 스택을 이용하여 구현
    Stack<Node<E>> stack = new Stack<>();
    // 방문 순서를 저장할 list
    List<E> result = new ArrayList<>();

    // root가 없으면 탐색 불가능
    if (root == null) {
        return result;
    }

    // root 노트를 스택에 넣기
    stack.push(root);

    // 스택이 빌 때까지 반복
    while (!stack.isEmpty()) {
        // 스택에서 노드를 하나 꺼냄
        Node<E> node = stack.pop();
        // root 방문 완료
        result.add(node.getData());

        // Stack은 LIFO(Last-In First-Out)
        // 즉, 좌측부터 탐색하기 위해 좌측을 나중에 넣는다.
        // 우측 자식 Node를 먼저 넣기
        if (node.getRight() != null) {
            stack.push(node.getRight());
        }
        // 좌측 자식 Node 넣기
        if (node.getLeft() != null) {
            stack.push(node.getLeft());
        }
    }

    return result;
}

// 순회하고, 방문한 순서를 LinkedList로 반환
public List<E> preorderDfsRecursion() {
    // 결과 저장용
    List<E> result = new ArrayList<>();

    // root 없으면 순회 불가능
    if (root == null) {
        return result;
    }

    // 재귀 시작
    preorderDfsHelper(root, result);
    return result;
}

private void preorderDfsHelper(Node<E> node, List<E> result) {
    // Node가 없을 때까지 재귀함.
    if (node == null) {
        return;
    }

    // 현재 노드를 우선 방문 처리
    result.add(node.getData());
    // 좌측 자식 노드 탐색
    preorderDfsHelper(node.getLeft(), result);
    // 좌측 노드 탐색이 다 끝나면 우측 자식 노드 탐색
    preorderDfsHelper(node.getRight(), result);
}

// 순회하고, 방문한 순서를 LinkedList로 반환
public List<E> inorderDfs() {
    // Stack 사용
    Stack<Node<E>> stack = new Stack<>();
    List<E> result = new ArrayList<>();

    if (root == null) {
        return result;
    }

    // 현재 노드를 저장
    Node<E> current = root;
    // 스택이 비거나, 현재 탐색할 노드가 없을 때까지 반복
    while (!stack.isEmpty() || current != null) {
        // 현재 노드를 stack에 넣어두고 가장 좌측 끝 노드까지 stack에 넣기
        while (current != null) {
            stack.push(current);
            current = current.getLeft();
        }

        // stack에서 꺼내서 저장
        Node<E> node = stack.pop();
        result.add(node.getData());

        // 만약 우측 자식노드가 있으면, 우측을 현재 탐색할 노드로 설정
        // 다음 루프에서 우측 자식노드의 제일 좌측 끝 노드부터 탐색
        if (node.getRight() != null) {
            current = node.getRight();
        }
    }

    return result;
}

// 순회하고, 방문한 순서를 LinkedList로 반환
public List<E> inorderDfsRecursion() {
    List<E> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    // Helper 함수 호출 시작
    inorderDfsHelper(root, result);
    return result;
}

private void inorderDfsHelper(Node<E> node, List<E> result) {
    if (node == null) {
        return;
    }

    // 우석 좌측부터 탐색
    inorderDfsHelper(node.getLeft(), result);
    // 좌측부터 탐색 후 현재 노드 방문 처리
    result.add(node.getData());
    // 현재 노드까지 방문하고 나서 우측 탐색
    inorderDfsHelper(node.getRight(), result);
}

// 순회하고, 방문한 순서를 LinkedList로 반환
public List<E> postorderDfs() {
    // 스택을 2개 사용함.
    // preorder와 비슷하게 root -> right -> left 순서로 방문
    // 방문한 순서를 stack에 쌓고 꺼내면 left -> right -> root 순서가 됨

    // 복잡하다면, stack이 아니라 list에 data를 넣은 뒤, list을 뒤집는 방식으로도 구현한 수 있음.
    // 해당 방식이 더욱 간단함.

    // 방문 예정을 저장하는 스택
    Stack<Node<E>> visitStack = new Stack<>();
    // 방문한 노드를 쌓아놓는 스택
    Stack<Node<E>> resultStack = new Stack<>();
    List<E> result = new ArrayList<>();

    if (root == null) {
        return result;
    }

    // root 부터 방문
    visitStack.push(root);

    // 방문 예정이 없을 때까지
    while (!visitStack.isEmpty()) {
        // 하나 꺼내기
        Node<E> node = visitStack.pop();
        // 일단 root 방문 처리
        resultStack.push(node);

        // Preorder와 반대로 우측부터 방문하기 위해 거꾸로 저장
        // 좌측을 방문 계획
        if (node.getLeft() != null) {
            visitStack.push(node.getLeft());
        }
        // 우측을 방문 계획
        if (node.getRight() != null) {
            visitStack.push(node.getRight());
        }
    }

    // 완료 후, 결과 스택을 뒤집어서 result에 저장
    while (!resultStack.isEmpty()) {
        // 하나씩 뽑아서 list에 넣기
        Node<E> node = resultStack.pop();
        result.add(node.getData());
    }

    return result;
}

// 재귀는 매우 간단함.
public List<E> postorderDfsRecursion() {
    List<E> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    // helper 호출
    postorderDfsHelper(root, result);
    return result;
}

private void postorderDfsHelper(Node<E> node, List<E> result) {
    if (node == null) {
        return;
    }

    // 좌측 방문하기
    postorderDfsHelper(node.getLeft(), result);
    // 좌측 방문 이후 우측 방문
    postorderDfsHelper(node.getRight(), result);
    // 우측 방문까지 완료된 후, 상위 노드 방문 처리
    result.add(node.getData());
}

// 너비 우선 탐색
public List<E> bfs() {
    // queue를 사용.
    // queue는 FIFO(First-In, First-Out)
    Queue<Node<E>> queue = new LinkedList<>();
    List<E> result = new ArrayList<>();

    // root을 먼저 enqueue
    queue.offer(root);

    // queue가 빌 때까지 반복
    while (!queue.isEmpty()) {
        // 큐에서 노드를 하나 꺼냄
        Node<E> node = queue.poll();
        // 꺼낸 노드를 방문 처리
        result.add(node.getData());

        // 꺼낸 노드의 자식들을 큐에 추가
        // 왼쪽 자식 추가
        if (node.getLeft() != null) {
            queue.offer(node.getLeft());
        }
        // 오른쪽 자식 추가
        if (node.getRight() != null) {
            queue.offer(node.getRight());
        }
    }

    return result;
}