프로그래머스: 시험장 나누기(실패)⭐⭐⭐⭐⭐

업데이트: 2024.07.14 Updated: 2024.07.14

카테고리: Programmers

태그: Algorithm, Blog, C++, Programmers

난이도 ⭐⭐⭐⭐⭐
유형 : ❓

🧐 문제

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리1 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다.

하나의 노드는 하나의 시험장을 나타냅니다.
검은 바탕의 흰 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다.

2-1. 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다.
노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다.

3-1. 위의 그림에서, 9번 시험장에는 10명, 4번 시험장에는 8명, 6번 시험장에는 20명의 응시자가 시험을 볼 예정입니다.
노드 사이의 간선은 해당 시험장이 연결되어 있음을 의미합니다.

4-1. 위의 그림에서, 9번 시험장은 7번 시험장과, 7번 시험장은 6번 시험장과 연결되어 있습니다.

코딩 테스트를 총괄하는 무지는 안정적인 시험을 위해, 시험장에서 오는 트래픽을 k개의 그룹으로 나누어 각 그룹별 서버로 분산시키기로 하였습니다. 시험장 사이를 연결한 간선들 중 k-1개를 끊어서 시험장을 k 개의 그룹으로 나눌 계획입니다. 이때, 그룹별 최대 트래픽을 최소화하기 위하여 가장 큰 그룹의 인원을 최소화시켜야 합니다.

위의 그림에서 7번과 6번 시험장을 잇는 간선을 끊고, 9번과 7번 시험장을 잇는 간선을 끊는다면, 전체 시험장은 3개의 그룹으로 나누어집니다.

주황색 노드로 표시된 A그룹의 인원은 35명(10+8+5+6+1+1+4)
보라색 노드로 표시된 B그룹의 인원은 37명(7+30)
녹색 노드로 표시된 C그룹의 인원은 40명(20+8+12)

즉, 인원이 가장 많은 그룹은 40명입니다. 다른 어떤 방법으로 시험장을 3개의 그룹으로 나눈다고 해도, 인원이 가장 많은 그룹의 인원이 40명 미만이 되도록 나눌 수는 없습니다.

나눌 그룹의 수를 나타내는 정수 k, 각 시험장의 응시자 수를 나타내는 1차원 정수 배열 num, 시험장의 연결 상태를 나타내는 2차원 정수 배열 links가 매개변수로 주어집니다. 인원이 가장 많은 그룹의 인원이 최소화되도록 k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ k ≤ 10,000
k ≤ num의 길이 ≤ 10,000
- num[i]에는 i번 시험장의 응시자 수가 담겨있습니다.
- 1 ≤ num의 원소 ≤ 10,000
links의 길이 = num의 길이
- links의 i번째 행은 i번 노드(시험장)의 [왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호]입니다.
  - 해당 위치에 자식 노드가 없는 경우 -1이 담겨있습니다.
  - 잘못된 노드 번호나, 하나의 이진 트리 구조가 아닌 입력은 주어지지 않습니다.

정확성 테스트 케이스 제한 사항

1 ≤ k ≤ 20
k ≤ num의 길이 ≤ 20

효율성 테스트 케이스 제한 사항

주어진 조건 외 추가 제한사항 없습니다.

입출력 예

k	num	links	result
3	[12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1]	[[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]]	40
1	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	27
2	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	14
4	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	9

제한시간 안내

정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

이진 트리 : 모든 노드들의 자식 노드가 두 개 이하인 트리

입출력 예 설명

펼치기 / 접기

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

나눌 그룹의 수가 1개 이므로, 주어진 트리를 나눌 수 없습니다.

보라색 노드로 표시된 유일한 그룹의 인원은 27명입니다.

입출력 예 #3

나눌 그룹의 수가 2개 이므로, 그림과 같이 1개의 간선을 끊어서 2개의 그룹으로 나눌 수 있습니다.

보라색 노드로 표시된 그룹은 13명, 주황색 노드로 표시된 그룹은 14명입니다. 따라서, 최대 그룹의 인원은 14명입니다.

입출력 예 #4

나눌 그룹의 수가 4개 이므로, 그림과 같이 3개의 모든 간선을 끊어서 4개의 그룹으로 나눌 수 있습니다.

최대 그룹의 인원은 9명입니다.

위와 같이 할인하면 4명의 이모티콘 플러스 가입자와 13,860원의 판매액을 달성할 수 있습니다. 다른 할인율을 적용하여 이모티콘을 판매할 수 있지만 이보다 이모티콘 플러스 서비스 가입자를 최대한 늘리면서, 이모티콘 판매액 또한 최대로 늘리는 방법은 없습니다.

따라서, [4, 13860]을 return 하면 됩니다.

✏️ 나의 풀이 (실패)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

// 루트 노드의 번호 찾기
int get_root_id(vector<vector<int>>& links) {
    int link_size = links.size();
    vector<int> v(link_size);
    
    for(vector<int> link : links) {
        if(link[0] != -1) v[link[0]] = 1;
        if(link[1] != -1) v[link[1]] = 1;
    }
    
    for(int i=0; i<link_size; i++) {
        if(v[i] == 0) return i;
    }
    return -1;
}

// 서브 트리 합 구하기
int get_tree(vector<int>& tree, vector<int> num, vector<vector<int>> links, int cur, int id) {
   
    int left = links[id][0];
    int right = links[id][1];
    
    tree[cur] = num[id];
    if(left != -1) {
        tree[cur] += get_tree(tree, num, links, cur*2, left);
    }
    if(right != -1) {
        tree[cur] += get_tree(tree, num, links, cur*2+1, right);
    }
    
    return tree[cur];   
}

// 간선 끊기
vector<int> nodes;

// 끊겨있는 자식 노드의 인원수만큼 반환
int bfs(vector<int>& tree, int root, int cur) {
    
    // 없는 노드면, 탈출
    if(tree[cur] == 0) return 0;
    if(nodes[cur] == 1 && cur != root) {
        return tree[cur];
    }
    
    return bfs(tree, root, cur*2) + bfs(tree, root, cur*2+1);
}

int get_result(vector<int>& tree, int n, int k) {

    nodes.resize(n+2);
    for(int i=1; i<=k; i++) {
        nodes[i] = 1;
    }
    
    // 모든 경우의 수 중에 그룹의 최대 인원수가 작은 것
    int min_group_nop = INT_MAX;
    
    // 모든 경우의 수
    do {
        
        // 그룹의 최대 인원수
        int max_group_nop = 0;
        
        // 각 그룹의 루트에서 반복 
        for(int i=1; i<n+1; i++) {
            if(tree[i] == 0) break;
            if(nodes[i] == 1) {
                int group_root = i;
                
                int group_nop = tree[group_root] - bfs(tree, group_root, group_root);
                
                max_group_nop = max(max_group_nop, group_nop);
                
            }
        }
        
        min_group_nop = min(max_group_nop, min_group_nop);
        
    }
    while(prev_permutation(nodes.begin()+2, nodes.begin()+n+2));
    
    return min_group_nop;
}

int solution(int k, vector<int> num, vector<vector<int>> links) {
 
    int root_id = get_root_id(links);
    
    vector<int> tree(42);
    get_tree(tree, num, links, 1, root_id);
    
    return get_result(tree, num.size(), k);
}

🧐 분석(실패한 이유)

노드의 개수가 10000개까지 가능하므로, 이진 트리를 연결 리스트로 구현해야만 했다.
위의 상황에선 Segment fault가 일어날 수 밖에 없다.
서브 트리를 나누고 최대 인원 수를 구하는 것이 아니라 최대 인원 수를 통해 서브 트리를 구하는 형태로 가야했다.
그런 이유로 메모리 초과가 일어날 수 밖에 없었다.

📜 한줄 평

AI 추천문제를 통해 풀어가고 있는데, Lv. 2~3 정도를 주다가 갑자기 Lv. 5를 주길래 풀어봤다가 하루를 통째로 날려먹었다.
컴퓨터알고리즘 수업 과제를 푸는 것 같아서 재밌긴 했지만 시간을 너무 잡아먹었다.
그런 탓에 실력을 더 키우고, 이 문제에 다시 도전해보려 한다.

그런데 다음 문제도 조금 무섭다…

햄랑