[프로그래머스 Level.4] 1,2,3 떨어트리기 (2023 KAKAO BLIND RECRUITMENT) (Java)
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/150364
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 1,2,3 떨어트리기
문제 설명
춘식이는 트리의 1번 노드에 숫자 1, 2, 3 중 하나씩을 계속해서 떨어트려 트리의 리프 노드1에 숫자를 쌓는 게임을 하려고 합니다.
아래 그림은 게임의 예시를 나타냅니다.
- 트리의 모든 간선은 부모 노드가 자식 노드를 가리키는 단방향 간선입니다.
- 모든 부모 노드는 자식 노드와 연결된 간선 중 하나를 길로 설정합니다.
- 실선 화살표는 길인 간선입니다.
- 점선 화살표는 길이 아닌 간선입니다.
- 모든 부모 노드는 자신의 자식 노드 중 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정합니다.
[게임의 규칙]은 아래와 같습니다.
- 1번 노드(루트 노드)에 숫자 1, 2, 3 중 하나를 떨어트립니다.
- 숫자는 길인 간선을 따라 리프 노드까지 떨어집니다.
- 숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊습니다.
- 만약 현재 길로 연결된 노드의 번호가 가장 크면, 번호가 가장 작은 노드를 가리키는 간선을 길로 설정합니다.
- 노드의 간선이 하나라면 계속 하나의 간선을 길로 설정합니다.
- 원하는 만큼 계속해서 루트 노드에 숫자를 떨어트릴 수 있습니다.
- 단, 앞서 떨어트린 숫자가 리프 노드까지 떨어진 후에 새로운 숫자를 떨어트려야 합니다.
[게임의 목표]는 각각의 리프 노드에 쌓인 숫자의 합을 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번 노드는 항상 루트 노드입니다.
- edges[i]는 [부모 노드 번호, 자식 노드 번호] 형태로, 단방향으로 연결된 두 노드를 나타냅니다.
- target의 길이 = edges의 길이 + 1
- target[i]는 i + 1번 노드에 쌓인 숫자의 합으로 만들어야 하는 수를 나타냅니다.
- 0 ≤ 리프 노드의 target값 ≤ 100
- 리프 노드를 제외한 노드의 target값 = 0
- target의 원소의 합은 1 이상입니다.
- target[i]는 i + 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] |
입출력 예 #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 해야 합니다.
- 리프 노드는 자식 노드가 없는 노드를 뜻합니다. ↩
나의 코드
import java.util.*;
class Solution {
public int[] solution(int[][] edges, int[] target) {
int[] answer = {};
// Node 배열 생성하고 Node 객체 담음(Node번호, 목표값)
Node[] nodes = new Node[target.length + 1];
for(int i=1; i<target.length+1; i++) {
nodes[i] = new Node(i, target[i-1]);
}
// 노드에 childeren에 자식노드 담음
for(int i=0; i<edges.length; i++) {
nodes[edges[i][0]].childNodes.add(nodes[edges[i][1]]);
}
// leaf노드를 담고 연결상태를 기준으로 경로 세팅
ArrayList<Node> leafs = new ArrayList<>();
for(int i=1; i<target.length+1; i++) {
if(nodes[i].initialize()) {
leafs.add(nodes[i]);
}
}
boolean finishDrop = false;
ArrayList<Node> drops = new ArrayList<>();
Node root = nodes[1];
while(!finishDrop) {
finishDrop = true;
// 경로가 바뀌면서 리프에 떨어지는 횟수를 하나씩 증가시키면서 마지막 for문 만족하면 종료
Node drop = root.getNextDropLeaf(); // 루트부터 시작해서 현재경로로 카드가 떨어질 리프노드를 구하고 경로 변경
drops.add(drop);
drop.dropCnt++;
// dropCnt가 targetVal보다 크면 불가능 (카드가 최소 1이므로 dropCnt가 더 크면 targetVal보다 무조건 크므로)
if(drop.dropCnt > drop.targetVal) return new int[] {-1};
// 모든 leaf의 dropCnt에 *3을 했을 때 leaf의 목표값 이상이면 완료
// 카드가 최대 3이므로 3으로 해당 회수만큼 떨궈서 leaf의 목표값이 되면 되므로
for(Node leaf : leafs) {
if(3 * leaf.dropCnt < leaf.targetVal) {
finishDrop = false;
break;
}
}
}
answer = new int[drops.size()];
for(int i=0; i<answer.length; i++) {
answer[i] = drops.get(i).getCardVal();
}
return answer;
}
class Node {
int idx;
int targetVal;
int dropCnt;
boolean isLeaf = false;
ArrayList<Node> childNodes = new ArrayList<>();
Node road = null;
Node next = null;
Node(int idx, int targetVal) {
this.idx = idx;
this.targetVal = targetVal;
}
boolean initialize() {
if(childNodes.size() == 0) {
isLeaf = true;
return isLeaf;
}
Collections.sort(childNodes, (o1, o2) -> o1.idx - o2.idx);
// 연결된 경로 세팅 (road는 현재 노드에서 연결된 경로의 노드, next는 연결된 경로의 노드가 경로바 바꼈을 때의 다음 노드)
// 예를 들어 처음 세팅 때 1번 노드의 road는 2번 노드이고 2번 노드의 next는 3번 노드이다.
Node temp = null;
for (Node child : childNodes) {
if (road == null) {
road = child;
temp = road;
} else {
temp.next = child;
temp = temp.next;
}
}
temp.next = road;
return isLeaf;
}
Node getNextDropLeaf() {
if(isLeaf) {
return this;
} else {
Node temp = road.getNextDropLeaf();
road = road.next;
return temp;
}
}
int getCardVal() {
dropCnt--;
int val = Math.max(1, targetVal - 3 * dropCnt);
targetVal -= val;
return val;
}
}
}
풀이
- 트리를 생성하고 세팅한 다음 숫자를 떨어트릴 때마다 간선을 변화하고 숫자 값을 구하는 것을 구현하는 것이 어려운 문제였다.
- Node 배열 nodes를 생성하고 target을 순회하면서 노드의 번호와 노드의 목표 점수를 담아준다.
- 그리고 edges를 순회하면서 노드의 자식에 연결된 해당 노드들을 담아준다.
- Node 클래스에 구현한 initialize() 메소드를 이용하여 리프 노드를 구하여 leafs 리스트에 담고 초기에 간선으로 연결된 노드들을 구하여 roaddp 담고 숫자가 지나간 다음에 연결된 노드들을 각각 노드의 next에 담는다.
- 그리고 이제 root 노드(1번 노드)부터 시작하여 leaf 노드까지 연결된 road로 숫자를 떨어트리고 road를 각각 노드의 next로 변경시키면서 반복한다. Node 클래스에 구현한 getNextDropLeaf() 메소드를 이용하여 root 노드(1번 노드)부터 시작하여 리프 노드가 나올 때까지 해당 노드의 road 노드로 getNextDropLeaf()를 재귀 호출하고 해당 road 노드를 road 노드의 next로 변경하여 리프 노드를 구한다. 그리고 리프 노드의 dropCnt를 증가시키고 drops 리스트에 담아준다. 해당 노드의 dropCnt가 해당 노드의 targetVal 보다 크다면 숫자 1을 계속 떨어트려도 targetVal을 넘어버리기 때문에 무조건 targetVal보다 커지므로 -1을 반환한다.
- while문을 종료시킬 수 있는지 확인하기 위해 while문을 반복할 떄마다 매번 leafs를 순회하면서 모든 leaf 노드의 dropCnt * 3이 해당 leaf 노드의 targetVal 이상이라면 targetVal을 맞출 수 있기때문에 while문을 종료하면 된다.
- 이제 모든 리프 노드의 targetVal을 맞출 수 있기 때문에 dropCnt에 해당하는 횟수의 각각 카드 숫자를 구하면 된다. drops 리스트를 순회하면서 Node 클래스에 구현한 getCardVal()을 이용하여 해당 노드에 떨어트릴 숫자를 구한다.
- drops를 순회하며 떨어트릴 숫자를 구할 때마다 answer에 차례로 저장한 후에 answer를 반환하면 된다.
참고 : https://school.programmers.co.kr/questions/42006