코딩테스트/코드챌린지

[2025 프로그래머스 코드챌린지 1차 예선] 홀짝트리 (Java)

haleylog 2025. 3. 6. 16:11

요구사항

1개 이상의 트리가 포함된 포레스트의 정보로 노드 리스트와 간선 리스트가 주어질때

각 노드는 홀수, 짝수, 역홀수, 역짝수 로 분류되고 어떤 노드를 루트노트로 설정하는지에 따라서 노드의 구분은 바뀔 수도 있다. 

노드의 숫자가 홀수이고 자식 노드 수가 홀수이면 홀수 노드

노드의 숫자가 홀수이고 자식 노드 수가 짝수이면 역홀수 노드

노드의 숫자가 짝수이고 자식 노드 수가 짝수이면 짝수 노드

노드의 숫자가 짝수이고 자식 노드 수가 홀수이면 역짝수 노드

이를 기준으로 트리의 성격을 판단한다.

홀수 노드와 짝수 노드로만 이루어진 트리는 홀짝트리가 되고 역홀수, 역짝수로만 이루어진 경우 역홀짝트리 라고 할때

주어진 포레스트에서 가능한 홀짝 트리와 역홀짝 트리의 갯수 구하기

 

 

입력 값

int[] nodes 노드 번호가 담긴 배열
nodes[i] 는 i+1 번째 노드의 번호이다. (순서는 무작위)
int[][] edges 노드와 노드간의 간선 정보가 담긴 배열
edges[i] 는 노드 번호가 2개 담겨있다
edges[i][0] 과 edges[i][1] 은 서로 연결되어 있다는 표시 

 

 

풀이

1. 각 노드의 자식노드 정보를 저장하기 위한 Map을 만들고 빈 list로 초기화

 

2. 간선 정보를 활용하여 각 노드의 자식 노드를 저장

 

3. 각 노드를 루트노드로 가정하고 루트노드의 성격에 따라서 각 노드 리스트에 저장

    -> 노드의 홀짝과 자식노드 숫자의 홀짝이 동일한 경우 yellowTree 리스트에 저장

    -> 노드의 홀짝과 자식노드 숫자의 홀짝이 다른 경우 redTree 리스트에 저장

 

4. 자식 노드 탐색 하기 (DFS)

    -> 자식 노드의 성격과 루트노드의 성격이 다른 경우 해당 Tree 리스트에서 삭제 처리

    -> 자식 노드의 자식 탐색 시 부모노드 정보도 들어있기 때문에 부모노드 탐색은 제외 처리

    -> 이미 Tree 리스트에서 제거된 루트 노드인 경우 자식 노드 탐색 중단

 

5. 모든 노드의 자식 루트를 탐색할 때 까지 3~4 반복

 

6. yellowTree 리스트 길이와 redTree 리스트 길이 return

 

728x90

Java 코드

import java.util.*;

class Solution {
    static List<Integer> yellowTree = new ArrayList<>();
    static List<Integer> redTree = new ArrayList<>();
    
    public int[] solution(int[] nodes, int[][] edges) {
        int[] answer = {};
        
        Map<Integer, List<Integer>> childsInfo = new HashMap<>();
        boolean isYellow;
        
        for(int node : nodes) {
            childsInfo.put(node, new ArrayList<>());
        }
        
        for(int[] edge : edges) {
            childsInfo.get(edge[0]).add(edge[1]);
            childsInfo.get(edge[1]).add(edge[0]);
        }
        
        for(int node : nodes) {
            isYellow = node%2 == childsInfo.get(node).size()%2;
            if(isYellow) yellowTree.add(node);
            else if(childsInfo.get(node).size() > 0) redTree.add(node);
            
            findChilds(node, node, node, childsInfo, isYellow);
        }
        
        answer = new int[]{yellowTree.size(), redTree.size()};
        
        return answer;
    }
    
    private void findChilds(int rootNode, int parentNode, int node, Map<Integer, List<Integer>> childsInfo, boolean isRootYellow) {
        List<Integer> childs;
        
        for(int childNode : childsInfo.get(node)) {
            if(childNode == parentNode) continue;
            if(yellowTree.indexOf(rootNode) == -1 && redTree.indexOf(rootNode) == -1) break;
            
            childs = childsInfo.get(childNode);
            
            if(isRootYellow != (childNode%2 == (childs.size()-1)%2)) { 
                if(isRootYellow) yellowTree.remove(yellowTree.indexOf(rootNode));
                else redTree.remove(redTree.indexOf(rootNode));
                return;
            } 
            
            findChilds(rootNode, node, childNode, childsInfo, childNode%2 == (childs.size()-1)%2);
        }
    }
}

 

 

문제 출처

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

728x90
반응형