[해커랭크(HackerRank) JAVA 풀이] - Java Visitor Pattern

해커랭크 - https://www.hackerrank.com/
Prepare > Java > Advanced > Java Visitor Pattern

HackerRank

 

 

Note : 이 문제에서는 스스로 출력을 생성해서는 안 됩니다. 그러한 솔루션은 규칙에 위배되는 것으로 간주되며 작성자는 실격됩니다. 솔루션의 출력은 솔루션 템플릿에서 제공되는 편집 불가능한 코드로 생성되어야 합니다.

객체 지향 프로그래밍에서 중요한 개념은 개방/폐쇄 원칙으로, 확장에는 열려 있지만 수정에는 폐쇄된 코드 작성을 의미합니다. 즉, 기존 코드를 수정하고 이를 사용하는 다른 코드를 잠재적으로 중단하는 대신 확장을 작성하여 새로운 기능을 추가해야 합니다. 이 과제는 개방/폐쇄 원칙을 적용할 수 있고 적용해야 하는 실제 문제를 시뮬레이션합니다.

루트 트리를 구현하는 Tree 클래스는 편집기에서 제공됩니다. 공개적으로 사용 가능한 다음과 같은 방법이 있습니다.

• getValue(): 노드에 저장된 값을 반환합니다.
• getColor(): 노드의 색상을 반환합니다.
• getDepth(): 노드의 깊이를 반환합니다. 노드의 깊이는 노드와 트리의 루트 사이의 가장자리 수이므로 트리의 루트에는 깊이가 있고 각 하위 노드의 깊이는 상위 노드의 깊이 +1과 같습니다.

이 챌린지에서 우리는 트리의 내부 구현을 수정에 대해 닫힌 것으로 취급하므로 직접 수정할 수 없습니다. 그러나 실제 상황과 마찬가지로 구현은 외부 클래스가 해당 기능을 확장하고 구축할 수 있도록 작성되었습니다. 보다 구체적으로 말하면 TreeVis 클래스(방문자 디자인 패턴)의 개체가 트리를 방문하고 accept 메서드를 통해 트리 구조를 통과할 수 있도록 합니다.

이 도전에는 두 부분이 있습니다.

 

Part I: Implement Three Different Visitors

각 클래스에는 구현을 작성해야 하는 세 가지 메서드가 있습니다.

1. getResult(): 각 클래스마다 다른 결과를 나타내는 정수를 반환합니다.
   ο SumInLeavesVisitor 구현은 나무 잎에 있는 값의 합계만 반환해야 합니다.
   ο ProductRedNodesVisitor 구현은 리프를 포함하여 모든 레드 노드에 저장된 값의 곱을 모듈로 10⁹ + 7로 계산하여 반환해야 합니다. 0 값의 곱은 1과 같습니다.
   ο FancyVisitor 구현은 짝수 깊이에서 나무의 잎이 아닌 노드에 저장된 값의 합계와 나무의 녹색 잎 노드에 저장된 값의 합계 간의 절대 차이를 반환해야 합니다. 0은 짝수임을 기억하십시오.
2. VisitNode(TreeNode 노드): getResult 메서드가 구현하는 클래스의 방문자에 대해 올바른 결과를 반환하도록 트리의 리프가 아닌 노드 방문을 담당하는 논리를 구현합니다.
3. VisitLeaf(TreeLeaf leaf): getResult 메소드가 구현 클래스의 방문자에 대해 올바른 결과를 리턴하도록 트리의 리프 노드 방문을 담당하는 로직을 구현하십시오.

 

Part II: Read and Build the Tree

각 노드에 1부터 n까지 번호가 매겨진 n-노드 트리를 읽습니다. 트리는 노드 값 목록(x₁, x₂, ... , xₙ), 노드 색상 목록(c₁, c₂, ... , cₙ) 및 가장자리 목록으로 제공됩니다. 이 트리를 Tree 클래스의 인스턴스로 구성합니다. 트리는 항상 노드 번호 1에 뿌리를 두고 있습니다.

세 방문자 클래스의 구현은 주어진 입력에서 빌드한 트리에서 테스트됩니다.

 

Input Format

첫 번째 줄에는 트리의 노드 수를 나타내는 단일 정수 n이 있습니다. 두 번째 줄에는 x₁, x₂, ... , xₙ의 각 값을 설명하는 n개의 공백으로 구분된 정수가 있습니다.
세 번째 줄에는 c₁, c₂, ... , cₙ의 각 값을 설명하는 공백으로 구분된 이진 정수가 포함됩니다. 각 cᵢ는 i번째 노드의 색상을 나타내며, 여기서 0은 빨간색, 1은 녹색을 나타냅니다.
n - 1개의 후속 라인 각각은 노드 uᵢ와 vᵢ 사이의 가장자리를 설명하는 두 개의 공백으로 구분된 정수 uᵢ와 vᵢ를 포함합니다.

 

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ xᵢ ≤ 10³
• cᵢ ∈ {0, 1}
• 1 ≤ vᵢ uᵢ ≤ n
• 트리가 노드 1에 뿌리를 두고 있음이 보장됩니다.

 

Output Format

편집기에서 잠긴 스텁 코드에 의해 처리되므로 stdout에 아무것도 인쇄하지 마십시오. 제공되는 세 가지 getResult() 메서드는 해당 클래스의 방문자(위에 정의됨)에 대한 결과를 나타내는 정수를 반환해야 합니다. ProductRedNodesVisitor의 getResult 메서드에서 반환된 값은 모듈로 10⁹ + 7로 계산되어야 합니다.

 

Sample Input

5
4 7 2 5 12
0 1 0 0 1
1 2
1 3
3 4
3 5

 

Sample Output

24
40
15

 

Explanation

 

 

 

[출처] https://www.hackerrank.com/challenges/java-vistor-pattern/problem

 

편집기의 잠긴 스텁 코드는 다음과 같이 세 가지 클래스 구현을 테스트합니다.

1. getResult 메서드가 트리의 잎 합계를 반환하는 SumInLeavesVisitor 개체를 만듭니다. 7 + 5 + 12 = 24입니다. 잠긴 스텁 코드는 반환된 값을 새 줄에 인쇄합니다.
2. getResult 메서드가 4 · 2 · 5 = 40인 빨간색 노드의 곱을 반환하는 ProductOfRedNodesVisitor 개체를 만듭니다. 잠긴 스텁 코드는 반환된 값을 새 줄에 인쇄합니다.
3. getResult 메서드가 짝수 깊이에서 비리프 노드 값의 합계와 녹색 리프 노드 값의 합계  |4 - (7 + 12)| = 15 간의 절대 차이를 반환하는 FancyVisitor 개체를 만듭니다. 잠긴 스텁 코드는 반환된 값을 새 줄에 인쇄합니다.

 

반응형

 

Code

import java.io.*;
import java.util.*;

enum Color {
    RED, GREEN
}

abstract class Tree {

    private int value;
    private Color color;
    private int depth;

    public Tree(int value, Color color, int depth) {
        this.value = value;
        this.color = color;
        this.depth = depth;
    }

    public int getValue() {
        return value;
    }

    public Color getColor() {
        return color;
    }

    public int getDepth() {
        return depth;
    }

    public abstract void accept(TreeVis visitor);
}

class TreeNode extends Tree {

    private ArrayList<Tree> children = new ArrayList<>();

    public TreeNode(int value, Color color, int depth) {
        super(value, color, depth);
    }

    public void accept(TreeVis visitor) {
        visitor.visitNode(this);

        for (Tree child : children) {
            child.accept(visitor);
        }
    }

    public void addChild(Tree child) {
        children.add(child);
    }
}

class TreeLeaf extends Tree {

    public TreeLeaf(int value, Color color, int depth) {
        super(value, color, depth);
    }

    public void accept(TreeVis visitor) {
        visitor.visitLeaf(this);
    }
}

abstract class TreeVis
{
    public abstract int getResult();
    public abstract void visitNode(TreeNode node);
    public abstract void visitLeaf(TreeLeaf leaf);

}

class SumInLeavesVisitor extends TreeVis {
    private int result = 0;
    public int getResult() {
        return result;
    }
    public void visitNode(TreeNode node) {}
    public void visitLeaf(TreeLeaf leaf) {
        result += leaf.getValue();
    }
}

class ProductOfRedNodesVisitor extends TreeVis {
    private long result = 1;
    private final int M = 1000000007;
    public int getResult() {
        return (int) result;
    }
    public void visitNode(TreeNode node) {
        if (node.getColor() == Color.RED) {
            result = (result * node.getValue()) % M;
        }
    }
    public void visitLeaf(TreeLeaf leaf) {
        if (leaf.getColor() == Color.RED) {
            result = (result * leaf.getValue()) % M;
        }
    }
}

class FancyVisitor extends TreeVis {
    private int nonLeafEvenDepthSum = 0;
    private int greenLeavesSum = 0;
    public int getResult() {
        return Math.abs(nonLeafEvenDepthSum - greenLeavesSum);
    }
    public void visitNode(TreeNode node) {
        if (node.getDepth() % 2 == 0) {
            nonLeafEvenDepthSum += node.getValue();
        }
    }
    public void visitLeaf(TreeLeaf leaf) {
        if (leaf.getColor() == Color.GREEN) {
            greenLeavesSum += leaf.getValue();
        }
    }
}

public class Solution {
    
    private static int[] nums;
    private static Color[] colors;
    private static HashMap<Integer, HashSet<Integer>> map;
    
    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        nums = new int[n];
        colors = new Color[n];
        map = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            colors[i] = sc.nextInt() == 0 ? Color.RED : Color.GREEN;
        }
        
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            
            HashSet<Integer> uNeighbors = map.get(u);
            if (uNeighbors == null) {                
                uNeighbors = new HashSet<>();
                map.put(u, uNeighbors);
            }
            HashSet<Integer> vNeighbors = map.get(v);
            if (vNeighbors == null) {
                vNeighbors = new HashSet<>();
                map.put(v, vNeighbors);
            }
            uNeighbors.add(v);
            vNeighbors.add(u);
        }
        sc.close();
        
        if (n == 1) {
            return new TreeLeaf(nums[0], colors[0], 0);
        }
        TreeNode root = new TreeNode(nums[0], colors[0], 0);
        addChildren(root, 1);
        return root;
    }

    private static void addChildren(TreeNode parent, Integer parentNum) {
        for (int treeNum: map.get(parentNum)) {
            map.get(treeNum).remove(parentNum);
            HashSet<Integer> grandChildren = map.get(treeNum);
            if ( grandChildren == null || grandChildren.isEmpty() ) {
                TreeLeaf leaf = new TreeLeaf(nums[treeNum-1], colors[treeNum-1], parent.getDepth()+1);
                parent.addChild(leaf);
                continue;
            }
            TreeNode node = new TreeNode(nums[treeNum-1], colors[treeNum-1], parent.getDepth()+1);
            addChildren(node, treeNum);
            parent.addChild(node);
        }
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Tree root = solve();
        SumInLeavesVisitor vis1 = new SumInLeavesVisitor();
        ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();
        FancyVisitor vis3 = new FancyVisitor();

        root.accept(vis1);
        root.accept(vis2);
        root.accept(vis3);

        int res1 = vis1.getResult();
        int res2 = vis2.getResult();
        int res3 = vis3.getResult();

        System.out.println(res1);
        System.out.println(res2);
        System.out.println(res3);
    }
}

 

 

방문자 패턴 (Visitor Pattern)
객체 지향 프로그래밍에서 객체의 구조와 기능을 분리하는 디자인 패턴.
객체들의 다양한 타입에 대해 새로운 동작을 추가하거나 수정할 때 객체 구조를 변경하지 않고 기능을 확장하기 위해 사용.
요소들과 기능이 분리되어 유지보수와 확장이 용이.

방문자 (Visitor)
새로운 기능을 구현한 클래스.
객체들을 방문하여 각 객체 타입에 따라 다른 동작을 수행하는 메서드를 가짐.

요소 (Element)
방문자가 방문하는 객체의 타입.
각 요소는 방문자를 받아들일 수 있는 메서드(accept)를 정의하고 방문자의 메서드를 호출.

구조 (Structure)
요소들의 구조.
보통 객체들이 서로 연결된 구조를 가짐.

동작 과정
방문자는 요소들을 방문하여 필요한 동작을 수행.
각 요소는 방문자를 자신에게 받아들이는 accept 메서드를 가지고 있음.
방문자는 visit 메서드를 호출하여 요소를 처리.

구현
방문자 패턴을 인터페이스와 클래스를 통해 구현.
방문자 인터페이스에는 각 요소를 방문할 때 호출할 메서드를 선언.
요소들은 방문자를 받아들일 수 있는 accept 메서드를 구현, 방문자의 메서드를 호출.

 

 

개인 공부를 위한 포스팅입니다.
모든 번역, 코드는 완벽하지 않을 수 있습니다.