[hackerrank] Organizing Containers of Balls

www.hackerrank.com/challenges/organizing-containers-of-balls/problem

Organizing Containers of Balls | HackerRank

문제풀이

1. 각 컨테이너에 같은 한 가지 타입의 볼만 존재하도록 만들 수 있는가를 묻는 문제이다.

 

2. 처음에는 swap을 이용하여 현재 컨테이너의 볼만 존재하도록 실행했으나, 볼의 개수가 10^9를 차지하는 경우가 존재하여 너무 큰 시간 초과가 날 것 같았다.

 

3. 다음은 현재 컨테이너의 크기를 구하고, 각 볼의 갯수를 새어 매핑 시 킬 수 있다면, swap으로 채워 넣을 수 있다고 말할 수 있기 때문에 더 빨라졌다.

 

소스코드

typedef unsigned int uint;
string organizingContainers(vector<vector<int>> container) {
    int containerCount = container.size();
    vector<uint> containerTotal(containerCount, 0);
    vector<uint> containerBallTotal(containerCount, 0);
    for (int i = 0; i < containerCount; i++) {
        for (int j = 0; j < container[i].size(); j++) {
            if (container[i][j] == 0) continue;
            containerTotal[i] += (uint)container[i][j];
            containerBallTotal[j] += (uint)container[i][j];
        }
    }
    vector<uint>::iterator it;
    for (int i = 0; i < containerCount; i++) {
        it = find(containerBallTotal.begin(), containerBallTotal.end(), containerTotal[i]);
        if (it == containerBallTotal.end()) return "Impossible";
        containerBallTotal.erase(it);
    }
    return "Possible";
}