[HackerRank] Organizing Containers of Balls

1. Problem

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

2. Feedback

• 수학적으로 풀어야한다는건 알았는데 못풀었음. Swap 을 해서 같은 종류의 공을 가질 수 있는지에 대한 확실한 풀이를 못찾았음.
• 답을 보니 container 가 가지는 공의 합과 BallType 의 합이 같으면, Possible 임.
• container 가 가지는 공의 합과 BallType 의 합이 정렬했을 때 같다면, Swap 을 했을 때, Possible 이라는 것을 알 수 있음.
• container 끼리 서로 가지고 있는 교환하여 BallType 의 개수에 맞추는 것이 핵심
• 결국 container 의 합을 정렬한 것 = BallType 의 합 정렬이 성립. swap 하면서 정렬한 것과 똑같이 만들 수 있기에

3. Source

public class OrganizingContainersOfBalls
{
	public static void main(String [] args)
	{
		Scanner in = new Scanner(System.in);
		int q = in.nextInt();
		for (int i = 0; i < q; i++)
		{
			int n = in.nextInt();
			int container[] = new int[n];
			int ballType[] = new int[n];
			for (int k = 0; k < n; k++)
			{
				for (int j = 0; j < n; j++)
				{
					int x = in.nextInt();
					container[k] += x;
					ballType[j] += x;
				}
			}
			System.out.println(solve(container, ballType));
		}
	}

	public static String solve(int container[], int ballType[])
	{
		Arrays.sort(container);
		Arrays.sort(ballType);
		if (Arrays.equals(container, ballType))
			return "Possible";
		else
			return "Impossible";
	}
}