[알고리즘문제] 릿코드 Employee Importance 문제풀이실패

leetcode.com/problems/employee-importance/

Employee Importance - LeetCode

직원의 ID, 중요도, 직속부하직원의 ID가 포함된 직원 정보의 데이터구조가 정의된다.

어떤 직원의 중요도는 해당 직원의 중요도와 직속부하직원의 중요도의 합이다.

직원객체의 배열과, 직원ID를 argument로 넘겨주면 해당 직원의 중요도를 return 하도록 하는 문제이다.,

아래와 같이 코드를 작성했다.

#include<iostream>
#include<vector>

using namespace std;

class Employee {
private:
    int id;
    int importance;
    vector<int> subordinates;
    
public:
    Employee(int id, int importance, vector<int> subordinates) {
        this->id = id;
        this->importance = importance;
        this->subordinates = subordinates;
    }
    int getId() {
        return id;
    }
    int getImportance() {
        return importance;
    }
    vector<int> getSub() {
        return subordinates;
    }
};

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        int importance = 0;
        vector<int> subordinate;
        for (int i = 0; i < employees.size(); i++) {
            if (id != employees[i]->getId()) continue;

            //중요도 합
            importance += employees[i]->getImportance();
            
            for (int j = 0; j < employees[i]->getSub().size(); j++) {
                subordinate.push_back(employees[i]->getSub()[j]);
            }
            break;
        }
        for (int i = 0; i < subordinate.size(); i++) {
            for (int j = 0; j < employees.size(); j++) {
                if (subordinate[i] != employees[j]->getId()) continue;

                importance += employees[j]->getImportance();
            }
        }
        
        return importance;
    }
};

int main() {
    vector<vector<int>> subordinates = {
        {2, 3, 4},
        {},
        {}
    };
    Employee* first = new Employee(1, 5, subordinates[0]);
    Employee* second = new Employee(2, 3, subordinates[1]);
    Employee* third = new Employee(3, 3, subordinates[2]);
    vector<Employee*> vEmp;
    vEmp.push_back(first);
    vEmp.push_back(second);
    vEmp.push_back(third);

    Solution solution;
    cout << solution.getImportance(vEmp, 1);

    delete first;
    delete second;
    delete third;
    
    return 0;
}

요렇게 작성했다.

로컬IDE에서는 잘 작동 되지만 릿코드에서 실행시킬 경우 컴파일 오류가 난다.

위의 코드처럼 작성하면 안되나 보다. 릿코드 사이트의 입문단계라 어떻게 코드를 작성해서 제출해야되는지에 대한 이해가 부족해서 난 문제같다.

//leetCode 초기상태
/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        
    }
};

아마 주석처리된 Employee는 릿코드 자체적으로 내장되어있는 객체인것 같다고 판단했다.

(요기까지 생각하는데 1시간 넘게 걸린듯..... ㅜ)

그래서 소스코드를 다시 작성했다.

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        int importance = 0;
        vector<int> subordinate;

        for (int i = 0; i < employees.size(); i++) {
            importance += employees[i]->importance;
        
            for (int j = 0; j < employees[i]->subordinates.size(); j++) {
                subordinate.push_back(employees[i]->subordinates[j]);
            }
            break;
        }
        for (int i = 0; i < subordinate.size(); i++) {
            for (int j = 0; j < employees.size(); j++) {
                if (subordinate[i] != employees[j]->id) continue;
            
                importance += employees[j]->importance;
            }
        }
                    
        return importance;
    }
};


int main() {
    vector<vector<int>> subordinates = {
        {2, 3},
        {4},
        {},
        {}
    };
    Employee* first = new Employee;
    first->id = 1; first->importance = 5; first->subordinates = subordinates[0];

    Employee* second = new Employee;
    second->id = 2; second->importance = 3; second->subordinates = subordinates[1];

    Employee* third = new Employee;
    third->id = 3; third->importance = 4; third->subordinates = subordinates[2];

    Employee* forth = new Employee;
    forth->id = 4; forth->importance = 1; forth->subordinates = subordinates[3];

    vector<Employee*> vEmp;
    vEmp.push_back(first);
    vEmp.push_back(second);
    vEmp.push_back(third);

    Solution solution;
    cout << solution.getImportance(vEmp, 1);

    delete first;
    delete second;
    delete third;
    
    return 0;
}

이제 컴파일은 된다. 하지만 잘못된 값을 반환하고 있다.ㅜ

답을 보니 input된 employee ID에 대한 직속부하 뿐만아니라 직속의 직속부하의 중요도도 체크해야 되는듯 하다..

 

 

 

오전 11시 40분 ~ 오후 8시 47 릿코드 EZ문제를 9시간정도에 걸쳐 풀어보았지만 문제풀이 실패....

알고리즘만 붙잡고 있을수는 없으므로...

나중에 다시풀어봐야될듯.

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>

using namespace std;

//class Employee {
//private:
//    int id;
//    int importance;
//    vector<int> subordinates;
//    
//public:
//    Employee(int id, int importance, vector<int> subordinates) {
//        this->id = id;
//        this->importance = importance;
//        this->subordinates = subordinates;
//    }
//    int getId() {
//        return id;
//    }
//    int getImportance() {
//        return importance;
//    }
//    vector<int> getSub() {
//        return subordinates;
//    }
//};

//class Solution {
//public:
//    int getImportance(vector<Employee*> employees, int id) {
//        int importance = 0;
//        vector<int> subordinate;
//        for (int i = 0; i < employees.size(); i++) {
//            if (id != employees[i]->getId()) continue;
//
//            //중요도 합
//            importance += employees[i]->getImportance();
//            
//            
//            for (int j = 0; j < employees[i]->getSub().size(); j++) {
//                subordinate.push_back(employees[i]->getSub()[j]);
//            }
//            break;
//        }
//        for (int i = 0; i < subordinate.size(); i++) {
//            for (int j = 0; j < employees.size(); j++) {
//                if (subordinate[i] != employees[j]->getId()) continue;
//
//                importance += employees[j]->getImportance();
//            }
//        }
//        
//        return importance;
//    }
//};

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        int importance = 0;
        for (int i = 0; i < employees.size(); i++) {
            if (employees[i]->id != id) continue;
            if (employees[i]->subordinates.size() == 0) {
                return employees[i]->importance;
            }
            importance = getSub(employees, i, importance, 0);
            break;
        }
        return importance;
    }

    int getSub(vector<Employee*> employees, int id, int total, int depth) {
        if (employees[id]->subordinates.size() == 0) {
            if(depth > 0) total += employees[id]->importance;
            return total;
        }
        int hap = 0;
        depth++;
        for (int i = 0; i < employees[id]->subordinates.size(); i++){
            if (i > 0) {
                depth++;
                hap += getSub(employees, employees[id]->subordinates[i] - 1, total, depth);
            }
            else {
                hap += getSub(employees, employees[id]->subordinates[i] - 1, total + employees[id]->importance, depth);
            }
            depth = 0;
        }
        return hap;
    }
};


int main() {
    vector<vector<int>> subordinates = {
        {2, 3},
        {4},
        {},
        {}
    };
    Employee* first = new Employee;
    first->id = 1; first->importance = 5; first->subordinates = subordinates[0];

    Employee* second = new Employee;
    second->id = 2; second->importance = 3; second->subordinates = subordinates[1];

    Employee* third = new Employee;
    third->id = 3; third->importance = 4; third->subordinates = subordinates[2];

    Employee* forth = new Employee;
    forth->id = 4; forth->importance = 1; forth->subordinates = subordinates[3];
    
    vector<Employee*> vEmp;
    vEmp.push_back(first);
    vEmp.push_back(second);
    vEmp.push_back(third);
    vEmp.push_back(forth);

    Solution solution;
    cout << solution.getImportance(vEmp, 1);

    delete first;
    delete second;
    delete third;
    delete forth;
    
    return 0;
}