현이의 개발 이야기

1, 2, 3 떨어뜨리기 - Lv. 4 문제 풀이

프로그래머스 > Java로 코테풀기2024. 06. 17. 14:02

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

2023 카카오 블라인드의 문제이다.
트리 그림이 그려져 있지만 구현의 비중이 더 높았던 것 같다.

[취업과 이직을 위한 프로그래머스 문제 풀이 전략: 자바편]을 집필할 때 정말 신경 썼던 것이 가독성이다.
이 문제처럼 구현 비중이 높은 문제들을 특히 가독성을 생각하며 코드를 작성해야 한다.

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

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

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

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

문제 풀기

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

문제의 조건을 만족하는 트리 구현
어떤 순서로 리프 노드들에 숫자가 떨어지는지 구하기
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();
  }
}

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

여러 자식 노드들 중 하나의 자식만 참조할 수 있고,
한 번 참조한 이후에는 다음 자식 노드를 참조하게 됩니다.
또, 이 순서는 자식 노드의 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씩 깔아 두고, 나머지 숫자 remainder 구하기
remainder를 2로 나눈 몫이 숫자 3을 떨어뜨리는 횟수
remainder를 2로 나눈 나머지가 숫자 2를 떨어뜨리는 횟수
남은 시도들은 모두 숫자 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();
  }
}

로그인이 필요합니다.

로그인