[프로그래머스 C#] Lv.2 시소 짝꿍

1. 문제설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.

이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.

사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

2. 제한사항

● 2 ≤ weights의 길이 ≤ 100,000
● 100 ≤ weights[i] ≤ 1,000
          ○ 몸무게 단위는 N(뉴턴)으로 주어집니다.
          ○ 몸무게는 모두 정수입니다.

3. 입출력 예시

weights	return
[100,180,360,100,270]	4

4-1. 나의 풀이: 최대공약수와 최소공배수를 이용한 풀이(X => 시간초과로 실패)

• 예제 코드 및 몇 개의 테스트 코드는 통과했지만, 매개 변수인 배열의 길이가 많아질수록 계산이 몇 배는 많아져서 비효율적인 코드. 가장 중요한 건 가독성이 떨어짐.

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

	//기준이 되는 weight i.
	for (long i = 0; i < weights.Length-1; i++)
	{
    	//i와 비교될 무게 k.
		for (long k = i+1; k < weights.Length; k++)
		{
        
        	//무게가 같으면 answer++하고 다음 k로 continue.
			if(weights[i] == weights[k])
			{
				answer++;
				continue;
			}
            
            //최대공약수 gcd, 최소공배수 lcm
			long gcd = getgcd(weights[i], weights[k]);
			long lcm = weights[i] * weights[k] / gcd;

			//밑에 if문계산을 위해 최소공배수를 i와 k번째 weights로 나눈 값.
			long numi = lcm / weights[i];
			long numk = lcm / weights[k];
		
        	//for문이 한 바퀴 돌고 weights베열의 무게 값이 바뀌면 안되서 따로 할당.
			long wgti = 0;
			long wgtk = 0;

			//주어진 자리가 2,3,4m이기 때문에 num이 1이 나왔을 때의 if문.
			if (numi == 1 || numk == 1)
			{
				if(numi*2 <= 4 && numk*2 <= 4)
				{
					wgti = weights[i] * numi * 2;
					wgtk = weights[k] * numk * 2;

					if (wgti == wgtk) answer++;
				}
			}
			else if(numi <= 4 && numk <= 4)
			{
				if (weights[i] * numi == weights[k] * numk) answer++;
			}
		}
	}

	return answer;
}
//최대공약수와 최소공배수를 구하는 함수.
public long getgcd(long i, long k)
{
	if (i % k == 0) return k;
	else return getgcd(k, i % k);
}

 

4-2. 나의 풀이: HashSet을 이용한 풀이(X => 시간 초과로 실패)

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

	for (long i = 0; i < weights.Length-1; i++)
	{
		for (long k = i+1; k < weights.Length; k++)
		{
			if(weights[i] == weights[k])
			{
				answer++;
				continue;
			}

			HashSet<long> hsI = new HashSet<long>();
			HashSet<long> hsK = new HashSet<long>();
	
    		//공통 배수를 집어넣어주는 for문.
			for (int h = 2; h <= 4; h++)
			{
				hsI.Add(weights[i] * h);
				hsK.Add(weights[k] * h);
			}

			//IntersetWith() = 기준 해시와 할당 해시를 비교해서 같은 부분만 남겨두고 나머진 모두 제거.
			hsI.IntersectWith(hsK);

			//남은 같으 수의 개수만큼 answer에 추가.
			answer += hsI.Count;
		}
	}

	return answer;
}

 

5. 다른 사람 풀이

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

	int[] arr = new int[4001];

	Array.Sort(weights);

	int count = 0;
	int number = 0;

	foreach (int weight in weights)
	{
		arr[weight * 2]++;
		arr[weight * 3]++;
		arr[weight * 4]++;

		if (number == weight)
		{
			count++;
			answer -= count * 2;
		}
		else
		{
			number = weight;
			count = 0;
		}
	}

	foreach (int num in arr)
	{
		if (num > 1) answer += Function(num);
	}
            

	return answer;
}

public long Function(int num)
{
	long total = 0;
	for (int i = 1; i < num; i++) total += i;

	return total;
}

 

6. 배운 점

• for문이 중첩될수록 시간 복잡도가 크게 상승한다는 것을 알고 있었지만 이 정도로 오래 걸릴 줄은 몰랐다.
• 해시함수를 사용하면 박싱&언박싱 현상이 일어나기 때문에 전보다 몇 배는 더 오래걸린다.
• 다른 사람의 풀이를 보고 느낀점은 발상의 전환과 코드를 짤 때 너무 어렵게 생각하지 말자는 것이다.