[프로그래머스/Java] 1, 2, 3 떨어뜨리기 - Lv. 4 문제 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/150364

프로그래머스

 

2023 카카오 블라인드의 문제이다.

트리 그림이 그려져 있지만 구현의 비중이 더 높았던 것 같다.

 

[취업과 이직을 위한 프로그래머스 문제 풀이 전략: 자바편]을 집필할 때 정말 신경 썼던 것이 가독성이다.

이 문제처럼 구현 비중이 높은 문제들을 특히 가독성을 생각하며 코드를 작성해야 한다.

 

읽기 쉬운 코드는 로직에만 집중할 수 있으므로 이해하기 쉽고, 실수가 있어도 쉽게 잡아낼 수 있습니다.

- [취업과 이직을 위한 프로그래머스 문제 풀이 전략: 자바편] 中 -

 

구현 문제의 풀이 코드는 문제에서 요구하는 로직을 다뤄야 한다.

로직이 제대로 구현되었는지를 파악하고, 실수를 줄이기 위해서는 가독성은 필수 요소이다.

 

문제 전문 ↓

문제 설명

춘식이는 트리의 1번 노드에 숫자 1, 2, 3 중 하나씩을 계속해서 떨어트려 트리의 리프 노드 1에 숫자를 쌓는 게임을 하려고 합니다.

아래 그림은 게임의 예시를 나타냅니다.

 

• 트리의 모든 간선은 부모 노드가 자식 노드를 가리키는 단방향 간선입니다.
• 모든 부모 노드는 자식 노드와 연결된 간선 중 하나를 길로 설정합니다.
  
  • 실선 화살표는 길인 간선입니다.
  • 점선 화살표는 길이 아닌 간선입니다.
• 모든 부모 노드는 자신의 자식 노드 중 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정합니다.

[게임의 규칙]은 아래와 같습니다.

1. 1번 노드(루트 노드)에 숫자 1, 2, 3 중 하나를 떨어트립니다.
2. 숫자는 길인 간선을 따라 리프 노드까지 떨어집니다.
3. 숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊습니다.
   
   • 만약 현재 길로 연결된 노드의 번호가 가장 크면, 번호가 가장 작은 노드를 가리키는 간선을 길로 설정합니다.
   • 노드의 간선이 하나라면 계속 하나의 간선을 길로 설정합니다.
4. 원하는 만큼 계속해서 루트 노드에 숫자를 떨어트릴 수 있습니다.
   
   • 단, 앞서 떨어트린 숫자가 리프 노드까지 떨어진 후에 새로운 숫자를 떨어트려야 합니다.

 

[게임의 목표]는 각각의 리프 노드에 쌓인 숫자의 합을 target에서 가리키는 값과 같게 만드는 것입니다.

예를 들어, target이 [0, 0, 0, 3, 0, 0, 5, 1, 2, 3]일 경우 아래 표와 같은 의미를 가집니다.

노드 번호	노드에 쌓인 숫자의 합
1	0
2	0
3	0
4	3
5	0
6	0
7	5
8	1
9	2
10	3

target대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해서는 [2, 1, 2, 2, 1, 3, 3]순으로 숫자를 떨어트리면 됩니다.

아래 두 그림은 순서대로 1, 2번째 숫자 [2, 1]을 떨어트린 뒤의 길 상황을 나타냅니다.

 

• 숫자 2는 떨어지면서 1번 노드와 2번 노드를 지나갔습니다.
  
  • 1번 노드는 3번 노드를 가리키는 간선을 길로 설정합니다.
  • 2번 노드는 5번 노드를 가리키는 간선을 길로 설정합니다.
• 숫자 1은 떨어지면서 1번 노드, 3번 노드, 6번 노드를 지나갔습니다.
  
  • 1번 노드는 3번 노드보다 번호가 큰 노드를 가리키는 간선이 없으므로 다시 2번 노드를 가리키는 간선을 길로 설정합니다.
  • 3번 노드는 간선이 하나이므로 계속해서 6번 노드를 가리키는 간선을 길로 설정합니다.
  • 6번 노드는 9번 노드를 가리키는 간선을 길로 설정합니다.

 

아래 두 그림은 순서대로 3, 4번째 숫자 [2, 2]를 떨어트린 뒤의 길 상황을 나타냅니다.

아래 세 그림은 순서대로 5, 6, 7번째 숫자 [1, 3, 3]을 떨어트린 뒤의 길 상황을 나타냅니다.

각 리프 노드에 쌓인 숫자를 모두 더해 배열로 나타내면 target과 같습니다.

트리의 각 노드들의 연결 관계를 담은 2차원 정수 배열 edges, 각 노드별로 만들어야 하는 숫자의 합을 담은 1차원 정수 배열 target이 매개변수로 주어집니다. 이때, target 대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해 숫자를 떨어트리는 모든 경우 중 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우를 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, target대로 숫자의 합을 만들 수 없는 경우 [-1]을 return 해주세요.

제한사항

• 1 ≤ edges의 길이 ≤ 100
  
  • edges[i]는 [부모 노드 번호, 자식 노드 번호] 형태로, 단방향으로 연결된 두 노드를 나타냅니다.
    
    • 1 ≤ 노드 번호 ≤ edges의 길이 + 1
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 1번 노드는 항상 루트 노드입니다.
• target의 길이 = edges의 길이 + 1
  
  • target[i]는 i + 1번 노드에 쌓인 숫자의 합으로 만들어야 하는 수를 나타냅니다.
    
    • 0 ≤ 리프 노드의 target값 ≤ 100
    • 리프 노드를 제외한 노드의 target값 = 0
  • target의 원소의 합은 1 이상입니다.

입출력 예

edges	target	result
[[2, 4], [1, 2], [6, 8], [1, 3], [5, 7], [2, 5], [3, 6], [6, 10], [6, 9]]	[0, 0, 0, 3, 0, 0, 5, 1, 2, 3]	[1, 1, 2, 2, 2, 3, 3]
[[1, 2], [1, 3]]	[0, 7, 3]	[1, 1, 3, 2, 3]
[[1, 3], [1, 2]]		[0, 7, 1]

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다. 위의 설명처럼 [2, 1, 2, 2, 1, 3, 3]순으로 숫자를 떨어트리면 target과 같게 만들 수 있지만, 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우는 [1, 1, 2, 2, 2, 3, 3]입니다.

입출력 예 #2

[3, 2, 1, 1, 3]순으로 숫자를 떨어트리거나 [1, 1, 1, 1, 2, 1, 3]순으로 숫자를 떨어트려도 target과 같게 만들 수 있지만, 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우는 [1, 1, 3, 2, 3]입니다.

입출력 예 #3

예제 3번의 트리는 주어지는 edges의 순서만 다를 뿐, 예제 2번과 같은 트리입니다. 2번 노드에 쌓인 숫자의 합을 7로 만들면서 3번 노드에 쌓인 숫자의 합을 1로 만들도록 숫자를 떨어트리는 방법은 없습니다.
따라서 [-1]을 return 해야 합니다.

문제 풀기

이 문제는 알고리즘적으로 설명할 것은 크게 없습니다. 풀이도 아주 직관적입니다.

1. 문제의 조건을 만족하는 트리 구현
2. 어떤 순서로 리프 노드들에 숫자가 떨어지는지 구하기
3. target을 만들 수 있는 방법이 있는지 검사하기

알고리즘보다는 구현에 초점이 맞춰진 문제인 만큼, 시간 복잡도를 따져보는 것은 의미가 없을 듯 하여 구현에 대한 내용만 다루겠습니다.

트리 구성하기

문제에서 edges가 이차원 배열로 주어지고, 이를 이용해 트리를 구성해야 합니다.

 

트리는 노드로 구성되어 있습니다.

가장 단순한 노드는 다음의 멤버 필드를 가지고 있을 것입니다.

• index: 자신의 노드 번호.
• children: 자식 노드들 리스트.

또, 다음의 메서드를 가집니다.

• addChild(): 자식 노드 추가.
• isLeaf(): 리프 노드인지 검사.

여기까지 코드 ↓

private static class Node {
  public final int index;
  private final List<Node> children = new ArrayList<>();
  
  Node(int index) {
    this.index = index;
  }
  
  void addChild(Node child) {
    children.add(child);
  }
  
  void sortChild() {
    children.sort(Comparator.comparingInt(n -> n.index));
  }
  
  private boolean isLeaf() {
    return children.isEmpty();
  }
}

 

이 문제의 노드는 조금 특별합니다.

1. 여러 자식 노드들 중 하나의 자식만 참조할 수 있고,
2. 한 번 참조한 이후에는 다음 자식 노드를 참조하게 됩니다.
3. 또, 이 순서는 자식 노드의 index 순서를 따릅니다.

이에 따라 다음의 메서드를 정의합니다.

• trigger(): 연결된 노드를 따라 내려갔을 때 도착하는 리프 노드를 반환. 한 번 호출 후에는 다음 자식 노드를 참조.
• sortChild(): 등록된 자식 노드들을 index 순으로 정렬.

이 부분에 해당하는 코드 ↓

private int childIndex = 0;

Node trigger() {
  if (isLeaf()) {
    return this;
  }
  
  Node leaf = children.get(childIndex).trigger();
  childIndex = (childIndex + 1) % children.size();
  return leaf;
}

void sortChild() {
  children.sort(Comparator.comparingInt(n -> n.index));
}

 

완성된 Node 클래스는 다음과 같습니다.

private static class Node {
  public final int index;
  private final List<Node> children = new ArrayList<>();
  private int childIndex = 0;
  
  Node(int index) {
    this.index = index;
  }
  
  Node trigger() {
    if (isLeaf()) {
      return this;
    }
    
    Node leaf = children.get(childIndex).trigger();
    childIndex = (childIndex + 1) % children.size();
    return leaf;
  }
  
  void addChild(Node child) {
    children.add(child);
  }
  
  void sortChild() {
    children.sort(Comparator.comparingInt(n -> n.index));
  }
  
  private boolean isLeaf() {
    return children.isEmpty();
  }
}

 

문제에서 입력 받은 edges를 이용하여 Node로 구성된 트리를 만들어 주는 constructTree() 메서드를 다음과 같이 정의해 줍니다.

private static Node constructTree(int[][] edges) {
  Node[] nodes = new Node[edges.length + 1];
  for (int i = 0; i < nodes.length; i++) {
    nodes[i] = new Node(i);
  }
  
  for (int[] edge : edges) {
    nodes[edge[0] - 1].addChild(nodes[edge[1] - 1]);
  }
  
  for (Node node : nodes) {
    if (node == null) continue;
    node.sortChild();
  }
  
  return nodes[0];
}

 

이렇게 구성된 트리를 이용하면 숫자가 떨어지는 리프 노드의 순서를 구할 수 있습니다.

target 숫자를 만들 수 있는지 검사

리프 노드에 떨어지는 횟수가 너무 적거나 너무 많다면 해당 리프 노드에서 원하는 숫자를 만들 수 없습니다.

이를 관리하기 위해 노드별로 목표하는 target 숫자를 만드는 클래스 Target을 만들어줍니다.

Target 클래스는 다음과 같은 멤버 필드를 가지게 됩니다.

• value: 해당 노드의 target 숫자
• tries: 해당 노드에 숫자가 떨어진 횟수

이 두 값을 이용하면 다음의 연산을 할 수 있습니다.

• addTry(): 해당 노드에 숫자가 떨어진 횟수 1 증가
• isNotEnough(): 아직 target 숫자를 만들기에는 해당 노드에 숫자가 떨어진 횟수가 부족
  • 떨어진 횟수 x 3이 해당 횟수로 만들 수 있는 최대 숫자
• didTooManyTries(): target 숫자를 만들기에는 해당 노드에 숫자가 너무 많이 떨어짐
  • 떨어진 횟수 자체가 해당 횟수로 만들 수 있는 최소 숫자
• isSolved(): target 숫자를 만들 수 있을 만큼 해당 노드에 숫자가 떨어짐

여기까지 코드 ↓

private static class Target {
  public final int value;
  private int tries = 0;
  
  Target(int value) {
    this.value = value;
  }
  
  void addTry() {
    tries += 1;
  }
  
  boolean isNotEnough() {
    return value > tries * 3;
  }
  
  boolean didTooManyTries() {
    return value < tries;
  }
  
  boolean isSolved() {
    return !isNotEnough() && !didTooManyTries();
  }
}

target 숫자를 만들기 위해 떨어뜨려야 하는 숫자 순서 구하기

위의 Target 클래스를 이용해서 각 노드별로 숫자를 떨어뜨리는 횟수를 구할 수 있었습니다.

이 횟수를 이용해 이 노드에 숫자를 어떤 순서로 떨어뜨려야 하는지를 구해 봅시다.

 

 

사전 순으로 가장 앞선 숫자들을 구해야 하므로, 3을 최대한 많이 사용하고, 그 다음으로 2를 최대한 사용해야 합니다.

그렇게 함으로써 1을 사용하는 빈도가 늘어나고, 사전순으로 앞서게 됩니다.

 

예를 들어, 숫자 4개를 이용하여 9을 구성해야 하는 경우를 생각해 봅시다.

2-2-2-3, 1-2-3-3 등 여러 조합이 나올 수 있습니다.

하지만 이 중 가장 사전 순으로 앞선 것은 3을 가장 많이 사용한 1-2-3-3입니다.

 

 

이 로직을 구현해 봅시다.

숫자를 떨어뜨릴 때에는 최소 1씩은 떨어뜨려야 합니다.

따라서 1은 각 떨어뜨리는 시도 당 미리 깔아 두고, 나머지 숫자를 분배합니다.

 

예를 들어, 위와 같이 4번의 시도로 9를 만든다면, 4번 각각의 시도에 미리 다음과 같이 1을 깔아 둡니다.

> 1-1-1-1

 

 

이제 남은 숫자인 5를 분배하면 됩니다.

 

이미 1을 모두 깔아 두었기 때문에 3을 최대한 많이 사용하기 위해서는 남은 숫자를 2로 나누어 그 몫을 계산합니다.

2를 최대한 많이 분배하여 3을 만들어야 하기 때문입니다. 같은 이유로, 2로 나눈 나머지는 2를 사용하는 횟수가 됩니다.

1. 숫자를 떨어뜨리는 시도 당 1씩 깔아 두고, 나머지 숫자 remainder 구하기
2. remainder를 2로 나눈 몫이 숫자 3을 떨어뜨리는 횟수
3. remainder를 2로 나눈 나머지가 숫자 2를 떨어뜨리는 횟수
4. 남은 시도들은 모두 숫자 1을 떨어뜨리는 횟수

여기에 해당하는 코드 ↓

int[] count = new int[3];
int remainders = value - tries;

count[2] = remainders / 2;  // 숫자 3을 떨어뜨리는 횟수
count[1] = remainders % 2;  // 숫자 2를 떨어뜨리는 횟수
count[0] = tries - count[1] - count[2];  // 숫자 1을 떨어뜨리는 횟수

 

이제 이 숫자들을 나열해 주어야 합니다.

배열로 만들 수도 있고, 리스트로 만들 수도 있을 텐데, 결정을 내리기 위해 이것들이 나중에 어떻게 사용될지를 생각해 봅시다.

 

각 리프 노드 별로 Target 클래스를 만들었고, 리프 노드를 방문하는 순서도 알고 있습니다.

또, 리프 노드 별로 사용되어야 하는 숫자들의 순서도 알고 있죠.

 

리프 노드를 방문하는 순서를 따라가면서, 사용되어야 하는 숫자들을 하나씩 사용하면 됩니다.

즉, 선입선출을 갖는 자료 구조인 큐를 사용하는 것이 적합해 보입니다.

 

위에서 구현한 로직을 이용해 큐를 구성하여 반환하는 solve() 메서드를 작성해 줍니다.

Queue<Integer> solve() {
  int[] count = new int[3];
  int remainders = value - tries;
  count[2] = remainders / 2;
  count[1] = remainders % 2;
  count[0] = tries - count[1] - count[2];
  
  Queue<Integer> q = new LinkedList<>();
  for (int i = 0; i < count.length; i++) {
    for (int j = 0; j < count[i]; j++) {
      q.add(i + 1);
    }
  }
  return q;
}

solution 메서드

마지막으로 이 모든 단계를 조합하여 문제를 해결해 줍니다.

private static boolean checkAll(Target[] targets, Function<Target, Boolean> map) {
  for (Target t : targets) {
    if (t.value == 0) continue;
    if (!map.apply(t)) {
      return false;
    }
  }
  return true;
}

public int[] solution(int[][] edges, int[] target) {
  Node tree = constructTree(edges);
  
  List<Integer> leaves = new ArrayList<>();
  Target[] targets = Arrays.stream(target).mapToObj(Target::new).toArray(Target[]::new);
  do {
    int leaf = tree.trigger().index;
    leaves.add(leaf);
    targets[leaf].addTry();
    
    if (checkAll(targets, Target::didTooManyTries)) {
      return new int[] {-1};
    }
  } while (!checkAll(targets, Target::isSolved));
  
  List<Queue<Integer>> queues = Arrays.stream(targets).map(Target::solve).collect(Collectors.toList());
  return leaves.stream().mapToInt(leaf -> queues.get(leaf).poll()).toArray();
}

전체 코드

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Solution {
  private static class Node {
    public final int index;
    private final List<Node> children = new ArrayList<>();
    private int childIndex = 0;

    Node(int index) {
      this.index = index;
    }

    Node trigger() {
      if (isLeaf()) {
        return this;
      }

      Node leaf = children.get(childIndex).trigger();
      childIndex = (childIndex + 1) % children.size();
      return leaf;
    }

    void addChild(Node child) {
      children.add(child);
    }

    void sortChild() {
      children.sort(Comparator.comparingInt(n -> n.index));
    }

    private boolean isLeaf() {
      return children.isEmpty();
    }
  }

  private static class Target {
    public final int value;
    private int tries = 0;

    Target(int value) {
      this.value = value;
    }

    void addTry() {
      tries += 1;
    }

    boolean isNotEnough() {
      return value > tries * 3;
    }

    boolean didTooManyTries() {
      return value < tries;
    }

    boolean isSolved() {
      return !isNotEnough() && !didTooManyTries();
    }

    Queue<Integer> solve() {
      int[] count = new int[3];
      int remainders = value - tries;
      count[2] = remainders / 2;
      count[1] = remainders % 2;
      count[0] = tries - count[1] - count[2];

      Queue<Integer> q = new LinkedList<>();
      for (int i = 0; i < count.length; i++) {
        for (int j = 0; j < count[i]; j++) {
          q.add(i + 1);
        }
      }
      return q;
    }
  }

  private static Node constructTree(int[][] edges) {
    Node[] nodes = new Node[edges.length + 1];
    for (int i = 0; i < nodes.length; i++) {
      nodes[i] = new Node(i);
    }

    for (int[] edge : edges) {
      nodes[edge[0] - 1].addChild(nodes[edge[1] - 1]);
    }

    for (Node node : nodes) {
      if (node == null) continue;
      node.sortChild();
    }

    return nodes[0];
  }

  private static boolean checkAll(Target[] targets, Function<Target, Boolean> map) {
    for (Target t : targets) {
      if (t.value == 0) continue;
      if (!map.apply(t)) {
        return false;
      }
    }
    return true;
  }

  public int[] solution(int[][] edges, int[] target) {
    Node tree = constructTree(edges);

    List<Integer> leaves = new ArrayList<>();
    Target[] targets = Arrays.stream(target).mapToObj(Target::new).toArray(Target[]::new);
    do {
      int leaf = tree.trigger().index;
      leaves.add(leaf);
      targets[leaf].addTry();

      if (checkAll(targets, Target::didTooManyTries)) {
        return new int[] {-1};
      }
    } while (!checkAll(targets, Target::isSolved));

    List<Queue<Integer>> queues = Arrays.stream(targets).map(Target::solve).collect(Collectors.toList());
    return leaves.stream().mapToInt(leaf -> queues.get(leaf).poll()).toArray();
  }
}