[Python] Hackerrank. Organizing Containers of balls (Medium)

 

 

 

문제를 읽고 이게 뭔소린지 이해하는 과정이 제일 난이도가 높다. 풀이법 자체는 어렵지 않음.

 

즉 n * n Matrix가 주어지는데, 각각의 row는 n번째 container에 들어 있는 ball 정보를 의미한다.

각 row에 있는 배열은 'idx'번째 type의 ball이 몇 개 있는지를 의미한다.

 

예컨대 matrix = [[1,4], [2,3]] 이 주어졌다면

• matrix[0] = [1, 4] 라는 정보는 container 0번에는 0 type의 공이 1개 (matrix[0][0] = 1), 1 type의 공이 4개 (matrix[0][1] = 4) 라는 뜻이다.
• matrix[1] = [2, 3] 라는 정보는 container 1번에는 0 type의 공이 2개 (matrix[1][0] = 2), 1 type의 공이 3개 (matrix[1][1] = 3) 라는 뜻이다.

 

"container 간 1:1로 swap을 해서 모든 컨테이너에는 같은 타입의 공이 있어야만 한다" 라는 조건을 잘 생각해보면

• container 길이는 무조건 고정된다. 1:1 swap밖에 없으므로, 특정 container에 들어갈 수 있는 공의 총 갯수는 변동이 없다.
• 여러 타입의 공 갯수 중 '가장 갯수가 적은 타입의 공'이 있을 것이다.
  얘는 무조건 container 길이와 똑같아야만 swap으로 문제의 조건을 만족시킬 수 있다.
  • [[1,4], [2,3]] 을 다시 생각해보자. 0 type 공은 총 3개 있고, 1 type의 공은 총 7개가 있다. 0 type의 공이 3개로 가장 개수가 적다.
    그런데 container에 들어갈 수 있는 공 갯수는 5개이고, container는 무조건 한 종류의 공만 있어야 한다면?
    0 type으로 3개 채우면, 나머지 2개는 무조건 1이 필요하다.
  • 같은 이유로, 만약 container에 들어갈 수 있는 공 갯수는 최대 3개인데 특정 타입의 공 최솟값이 4개라면?
    container에 3개 채우면, 남은 하나는 무조건 다른 container에 들어갈 수밖에 없게 된다.

 

따라서 이 문제는

• matrix 순회하면서, 각 타입별 공의 총 갯수 & 각 컨테이너에 들어간 공 갯수를 확인한다.
• 각 컨테이너에 들어간 공 갯수를 확인해서, 가장 공 갯수가 적은 컨테이너를 확인한다.
• "가장 갯수가 적은 타입의 공 == 가장 길이가 작은 컨테이너" 라면 Possible, 아니면 Impossible.