[프로그래머스] 시소 짝꿍

1. 첫 번째 접근

1. 몸무게 순서대로 정렬한다.
2. 2명을 선택하는 조합을 만든다.
3. 몸무게를 나누어서 1, 4/3, 3/2, 2 인 두명을 찾는다
4. 크기순으로 정렬되어 있기 때문에 나눈 값이 2를 넘어선 이후에 나머지는 탐색하지 않는다.

public long solution(int[] weights)
{
	long answer = 0;
	float[] divideArr = new float[4] { 1f, 4 / 3f, 3 / 2f, 2f };
	// 1. 몸무게 순서대로 정렬한다.
    Array.Sort(weights);
    
	// 2. 2명을 선택하는 조합을 만든다
	for (int i = 0; i < weights.Length - 1; i++)
	{
		int index = 0;
		for(int j = i+1; j < weights.Length; j++)
		{
			// 3. 거리가 2,3,4 이기 때문에 가벼운 사람의 1배 4/3배 3/2배 2배인 사람 수를 체크한다.
			int minWeight = weights[i];
			int maxWeight = weights[j];
			float divide = maxWeight / (float)minWeight;
            
            //4. 크기순으로 정렬되어 있기 때문에 나눈 값이 2를 넘어선 이후에 나머지는 탐색하지 않는다.
			while (divide > divideArr[index])
			{
				index++;
				if (index > 3)
					break;
			}
            if (index >3)
				break;
			if (divide == divideArr[index])
				answer++;
		}
	}
	return answer;
}

결과 : 시도는 좋았지만 시간 초과 오류가 발생했다 (Nice try)

2. 두 번째 접근

1. 중복을 제거하기 위해 몸무게를 key 중복 개수를 value로 하는 dictionary 생성한다.
2. key값을 선회하면서 key값의 4/3배, 3/2배, 2배 값이 dictionary에 있는지 확인하고 만약 있다면 각 weight의 value값을 곱해서 answer에 추가한다.
3. 같은 weight의 사람끼리 선택하는 경우를 추가한다.

public long solution(int[] weights)
{
	long answer = 0;

	// 1. 중복을 제거하기 위해 몸무게를 key 중복 개수를 value로 하는 dictionary 생성한다.
	Dictionary<int, int> weightPeople = new Dictionary<int, int>();
	foreach(int weight in weights)
	{
		if (weightPeople.ContainsKey(weight))
			weightPeople[weight] += 1;
		else
			weightPeople[weight] = 1;
	}

	foreach(int weight in weightPeople.Keys)
	{
		long count = weightPeople[weight];
		
		// 2. key값을 선회하면서 key값의 4/3배, 3/2배, 2배 값이 dictionary에 있는지 확인한다.
		if (weight % 3 == 0 && weightPeople.ContainsKey(weight * 4 / 3))
			answer += count * weightPeople[weight * 4 / 3];
		if(weight % 2 == 0 && weightPeople.ContainsKey(weight * 3 / 2))
			answer += count * weightPeople[weight * 3 / 2];
		if(weightPeople.ContainsKey(weight * 2))
			answer += count * weightPeople[weight * 2];

		// 3. 같은 weight의 사람끼리 선택하는 경우를 추가한다.
		answer += count * (count - 1) / 2;
	}
	return answer;
}

결과 : 성공!!!

어려웠던 부분

• int * int를 할 때 값이 급격히 커지기 때문에 long으로 캐스팅 할 지 생각해야 한다.
• 나누기를 할 때 정수 자료형으로 받으면 소수점이 잘려서 통과가 될 수도 있기 때문에 정수형으로 받으려면 나머지가 있는지 체크를 해줘야 한다.