[해커랭크] organizing-containers-of-balls

문제

---

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

Organizing Containers of Balls | HackerRank

 

Swap을 통해서 하나의 컨테이너에 하나의 타입만 놓을 수 있는 지 판단하는 문제다.

 

풀이

---

완전 탐색으로 문제를 풀 수 있을 것 같은데 시간 복잡도가 너무 많이 나올 것 같은 문제는 보통 DP 아니면 그리디인 경우가 많은데,

이 문제는 점화식으로 풀 수 없을 것 같아 그리디로 생각을 하고 접근하였다.

 

방법은

해당 타입의 공을 하나의 컨테이너로 옮겼다는 가정하에 결과가 일치하는지 확인하면 된다.

 

알고리즘 순서

1. 열의 총합을 구한다.(컨테이너가 가지는 공 총합)

2. 행의 총합을 구한다.(타입 공이 한쪽으로 몰릴 경우 총합)

3. 오름 차순으로 정렬

4. 컨테이너가 가지는 공의 총합 = 타입 공이 한쪽으로 몰릴경우 총합 이면 Possible 아니면 Impossible

 

<OrganizingContainers 코드>

public static String organizingContainers(List<List<Integer>> container) {
// Write your code here

    int n = container.size();
    long[] sumRow = new long[n];
    long[] sumCol = new long[n];
    
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            sumCol[i] += container.get(i).get(j);
            sumRow[i] += container.get(j).get(i);
        }
    }
    
    
    Arrays.sort(sumCol);
    Arrays.sort(sumRow);
    
    for(int i = 0 ; i < n ; i++){
        if(sumCol[i] != sumRow[i]){ return "Impossible";}
    }
    
    return "Possible";
}