[C++] Programmers 시험장 나누기

문제 설명

 

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

프로그래머스

 

---

내 풀이 과정

 

첫 번째 시도

해당 문제는 최대 트래픽을 최소화하는 것이 목표이다. 

따라서 해당 문제는 최적값을 찾는 최적화 문제이다. 하지만 해당 문제를 결정 문제로 치환할 수 있다.

다시 말해, "최대 트래픽의 최소값을 찾아라" 라는 문제가 아닌 "최대 트래픽으로 n이 될 수 있는가?" 라는 문제로 바꾸기로 했다.

그래서 낮은 트래픽 n부터 시작하여, "최대 트래픽으로 n이 될 수 있는가?"라는 명제에 참이 될 때까지 n값을 늘려 가기로하였다.

 

우선 입력받은 데이터를 트리 형식으로 생성한 후, 각 트리들을 어떻게 분리할 지에 대해 생각하였다.

이 문제는 각 노드들을 하나씩 탐색하면서 수용 인원이 적절한 지를 체크해야 한다.

그래서 자식 노드를 먼저 순회하는 후위 순회(postorder) 형식으로 탐색하기로 하였다.

(순회 순서)

리프 노드에서 루트 노드까지, 각 노드의 수용 인원을 더하면서 내가 원하는 트래픽 n을 넘어 가는 지를 체크하였다.

1. 만약 인원의 합이 트래픽 n을 넘어가지 않는다면, 해당 그룹 그대로 상위 노드로 올라간다.

2. 하지만 인원의 합이 트래픽 n을 넘어가면 자식 노드 중 하나를 자르기로 하였다.

3. 그래도 인원의 합이 트래픽 n을 넘어가면 나머지 자식 노드도 자르기로 하였다.

 

1~3 과정을 전부 통과하지 않는다는 것은 애초에 지정한 트래픽 n이 시험장의 최대 수용 인원을 초과하였다는 의미이므로, 초기 트래픽 n을 "시험장 최대 수용 인원" 혹은 "(전체 인원) / (시험장 개수)" 중 더 큰 값으로 설정해주는 센스도 추가하였다.

 

 

첫 번째 코드

#include <string>
#include <vector>

using namespace std;

struct node {
    int count;
    int parent;
    int child[2];
};

int root_node, people_size, group_size;
int group_count;
bool success_flag;
vector <node> place(10000, {0, -1, {-1, -1}});

void setting(vector<int> num, vector<vector<int>> links) {
    int place_size = num.size();
    for(int i = 0; i < place_size; ++i) {
        // 탐색 초기값 최적화를 위한 작업
        if(num[i] > group_size) group_size = num[i];
        people_size += num[i];
        
        place[i].count = num[i];
        
        for(int j = 0; j < 2; ++j) {
            place[i].child[j] = links[i][j];
            if(links[i][j] == -1) continue;
            
            place[links[i][j]].parent = i;
        }
    }
}

void find_root(int now) {
    if(place[now].parent == -1) {
        root_node = now;
        return;
    }
    find_root(place[now].parent);
}

int find_ans(int now) {
    // 1. 리프 노드면 자신 시험장의 인원만을 반환
    int left_number = place[now].child[0];
    int right_number = place[now].child[1];
    if(left_number == -1 && right_number == -1) return place[now].count;
    
    // 2. 자식 노드 인원과 자신의 인원을 모두 수용 가능하다면 해당 인원 반환
    int left_count = (left_number == -1 ? 0 : find_ans(left_number));
    int right_count = (right_number == -1 ? 0 : find_ans(right_number));
    int now_count = place[now].count;
    int total_count = left_count + right_count + now_count;
    
    if(total_count <= group_size) return total_count;
        
    // 3-1. 만약 전부 수용이 안 된다면 인원이 더 많은 쪽을 먼저 자르기
    group_count++;
    if(left_count <= right_count) total_count -= right_count;
    if(left_count > right_count) total_count -= left_count;
    if(total_count <= group_size) return total_count;
    
    // 3-2. 그래도 수용이 안 되면 반대쪽도 자르기
    group_count++;
    if(left_count <= right_count) total_count -= left_count;
    if(left_count > right_count) total_count -= right_count;
    if(total_count <= group_size) return total_count;
}

int solution(int k, vector<int> num, vector<vector<int>> links) {
    people_size = group_size = 0;
    
    setting(num, links);
    find_root(0);
    
    if(people_size / k > group_size) group_size = people_size / k;
    
    for(; ; ++group_size) {
        group_count = 1;
        find_ans(root_node);
        if(group_count <= k)
            break;
    }
    
    return group_size;
}

 

 

첫 번째 결과

(51점!)

 

---

두 번째 시도

멍청한 시도

로직 자체는 괜찮은 것 같은데 코드를 좀 더 최적화 해야겠다는 생각이 들었다.

그러다 떠오른 방법이 있었다.

각 노드를 순회하는 과정 중 "1. 만약 인원의 합이 트래픽 n을 넘어가지 않는다면, 해당 그룹 그대로 상위 노드로 올라간다" 라는 단계가 있었다.

문제를 푸는 과정에서 해당 단계를 거쳐가는 구간이 있다면 트래픽 n값이 계속 바뀌어도 해당 단계는 무조건 통과한다는 것이다. 

(두 경우 모두 "1. 만약 인원의 합이 트래픽 n을 넘어가지 않는다면, 해당 그룹 그대로 상위 노드로 올라간다" 조건을 만족한다.)

그래서 해당 경우에는 자식 노드의 트래픽을 부모 노드로 전부 올리고, 해당 부모 노드를 리프노드로 바꾸려고 하였다.

그러나...

 

 

두 번째 시도

#include <string>
#include <vector>

using namespace std;

struct node {
    int count;
    int parent;
    int child[2];
};

int root_node, people_size, group_size;
int group_count;
vector <node> place(10000, {0, -1, {-1, -1}});

void setting(vector<int> num, vector<vector<int>> links) {
    int place_size = num.size();
    for(int i = 0; i < place_size; ++i) {
        // 탐색 초기값 최적화를 위한 작업
        if(num[i] > group_size) group_size = num[i];
        people_size += num[i];
        
        place[i].count = num[i];
        
        for(int j = 0; j < 2; ++j) {
            place[i].child[j] = links[i][j];
            if(links[i][j] == -1) continue;
            
            place[links[i][j]].parent = i;
        }
    }
}

void find_root(int now) {
    if(place[now].parent == -1) {
        root_node = now;
        return;
    }
    find_root(place[now].parent);
}
bool is_child_a_leaf(int now) {
    if(now == -1) return true;
    if(place[now].child[0] == -1 && place[now].child[1] == -1) return true;
    return false;
}

int find_ans(int now) {
    // 1. 리프 노드면 자신 시험장의 인원만을 반환
    int left_number = place[now].child[0];
    int right_number = place[now].child[1];
    if(left_number == -1 && right_number == -1) return place[now].count;
    
    // 2. 자식 노드 인원과 자신의 인원을 모두 수용 가능하다면 해당 인원 반환
    // 이때 자식 노드가 리프 노드라면 해당 노드도 리프 노드로 치환
    int left_count = (left_number == -1 ? 0 : find_ans(left_number));
    int right_count = (right_number == -1 ? 0 : find_ans(right_number));
    int now_count = place[now].count;
    int total_count = left_count + right_count + now_count;
    
    if(total_count <= group_size) {
        if(is_child_a_leaf(left_number) && is_child_a_leaf(right_number)) {
            place[now].child[0] = -1;
            place[now].child[1] = -1;
            place[now].count = total_count;
        }
        return total_count;
    }
        
    // 3-1. 만약 전부 수용이 안 된다면 인원이 더 많은 쪽을 먼저 자르기
    group_count++;
    if(left_count <= right_count) total_count -= right_count;
    if(left_count > right_count) total_count -= left_count;
    if(total_count <= group_size) return total_count;
    
    // 3-2. 그래도 수용이 안 되면 반대쪽도 자르기
    group_count++;
    if(left_count <= right_count) total_count -= left_count;
    if(left_count > right_count) total_count -= right_count;
    if(total_count <= group_size) return total_count;
}

int solution(int k, vector<int> num, vector<vector<int>> links) {
    people_size = group_size = 0;
    
    setting(num, links);
    find_root(0);
    
    if(people_size / k > group_size) group_size = people_size / k;
    
    for(; ; ++group_size) {
        group_count = 1;
        find_ans(root_node);
        if(group_count <= k)
            break;
    }
    
    return group_size;
}

 

 

두 번째 결과

(또 51점..!)

---

세 번째 시도

결과를 보고 다시 생각해보니 두 번째 시도는 굉장히 의미 없는 행동이라는 것을 알게 되었다.

의미 없는 시도를 의미 있게 쓰려고 한 행동이었는데, 그럴 바에야 의미가 있는 정보를 더 활용하는 것이 낫다는 것을 깨달았다.

그래서 이번에는 트래픽 n을 좀 더 유의미하게 변화를 주기 위해서 next_size 라는 변수를 추가하였다.

밑의 그림을 통해 생각해보자.

 

k = 2라고 가정하면, 해당 문제는 최대 트래픽을 3500으로 잡고 시작하게 된다.

당연하겠지만 이 문제의 최대 트래픽의 최적값은 5000이다.

하지만 1~2번째 코드를 보면, 이전 트래픽에서 1씩 더하는 방식이므로 총 1500번의 순회를 더 돌게 된다.

만약 이러한 구조가 여러번 나타나게 된다면 어떻게 될까?

당연히 무의미한 계산이 반복되므로 시간 초과가 날 수 밖에 없다.

 

그러면 어떻게 해야하는가?

find_ans 함수는 결국 "최대 트래픽이 n이 될 수 있는가?"를 체크하는 함수이다.

그래서 우리는 다음번 find_ans 함수에 "최대 트래픽이 (n+1)이 될 수 있는가?"를 체크하는 것이 아닌 "최대 트래픽이 n + (유의미한 값)"이 될 수 있는가?"를 체크해야 한다.

즉, 수용 가능한 트래픽이 기준치를 초과해서 노드 가지치기를 해야 할 때, 그 기준치를 넘은 정도를 저장해 다음번 find_ans에 활용하자는 것이다.

아마 밑의 코드를 보면 더 잘 이해될 것이다.

 

 

세 번째 코드

#include <string>
#include <vector>

using namespace std;

struct node {
    int count;
    int parent;
    int child[2];
};

int root_node, people_size, group_size, next_size;
int group_count;
vector <node> place(10000, {0, -1, {-1, -1}});

void setting(vector<int> num, vector<vector<int>> links) {
    int place_size = num.size();
    for(int i = 0; i < place_size; ++i) {
        // 탐색 초기값 최적화를 위한 작업
        if(num[i] > group_size) group_size = num[i];
        people_size += num[i];
        
        place[i].count = num[i];
        
        for(int j = 0; j < 2; ++j) {
            place[i].child[j] = links[i][j];
            if(links[i][j] == -1) continue;
            
            place[links[i][j]].parent = i;
        }
    }
}

void find_root(int now) {
    if(place[now].parent == -1) {
        root_node = now;
        return;
    }
    find_root(place[now].parent);
}

int find_ans(int now) {
    // 1. 자신이 리프 노드면 자신 시험장의 인원만을 반환
    int left_number = place[now].child[0];
    int right_number = place[now].child[1];
    if(left_number == -1 && right_number == -1) return place[now].count;
    
    // 2. 자식 노드 인원과 자신의 인원을 모두 수용 가능하다면 해당 인원 반환
    // 이때 자식 노드가 리프 노드라면 해당 노드도 리프 노드로 치환
    int left_count = (left_number == -1 ? 0 : find_ans(left_number));
    int right_count = (right_number == -1 ? 0 : find_ans(right_number));
    int now_count = place[now].count;
    int total_count = left_count + right_count + now_count;
    if(total_count <= group_size) return total_count;
        
    // 3-1. 만약 전부 수용이 안 된다면 인원이 더 많은 쪽을 먼저 자르기
    group_count++;
    if(total_count != group_size && next_size > total_count - group_size)
        next_size = total_count - group_size;
    if(left_count <= right_count) total_count -= right_count;
    if(left_count > right_count) total_count -= left_count;
    if(total_count <= group_size) return total_count;
    
    // 3-2. 그래도 수용이 안 되면 반대쪽도 자르기
    group_count++;
    if(total_count != group_size && next_size > total_count - group_size)
        next_size = total_count - group_size;
    if(left_count <= right_count) total_count -= left_count;
    if(left_count > right_count) total_count -= right_count;
    if(total_count <= group_size) return total_count;
}

int solution(int k, vector<int> num, vector<vector<int>> links) {
    people_size = group_size = 0;
    
    setting(num, links);
    find_root(0);
    
    if(people_size / k > group_size) group_size = people_size / k;
    
    for(; ; group_size += next_size) {
        group_count = 1;
        next_size = 987654321;
        find_ans(root_node);
        if(group_count <= k)
            break;
    }
    
    return group_size;
}

 

 

세 번째 결과

 

결국 맞았다..!