[프로그래머스] Java 코딩테스트 - 순서쌍의 개수

순서쌍의 개수

✅ 문제 설명

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

✅ 제한사항

1 ≤ n ≤ 1,000,000

🔽 소스코드 1

💻 풀이

• 나머지 연산자를 활용해 n % i 가 0일 경우 count++ 를 통해 순서쌍을 계산해준다.

❗ 이 풀이의 가장 큰 문제는 작은 수는 괜찮지만 큰 수를 시간복잡도가 높아진 다는 점이다.
그래서 이를 해결할 수 있도록 반복의 수를 줄일 수 있는 방법으로도 풀이를 해보았다.

⌛ 시간 0.01ms ~ 8.17ms

	public int solution(int n) {
		int count = 0;
		for(int i = 1; i <= n; i++) {
			if(n % i == 0) {
				count++;
			}
		}
		return count;
	}

🔽 소스코드 2 (시간복잡도 해결)

💻 풀이

• 약수들을 쌍을 이루기 때문에 i 가 n 의 약수이면 n / i 도 약수이게 된다.

• 예를들어 20 의 경우 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1)이고, 36일 경우 (6, 6)을 제외하면 쌍을 이루게 된다.

• 그렇기 때문에 i * i가 n 보다 작거나 같을 때까지 반복문을 실행해 주고 count를 2씩 더해준다.

• 하지만 만약 동일한 숫자일 경우에는 2가 아닌 1만 더해야 하기 때문에 count를 -1 해주었다.

• 이렇게 진행할 경우 코드는 조금 더 길어지지만 시간복잡도가 해결되는 것을 확인해볼 수 있었다!

⌛ 시간 0.02ms ~ 0.04ms

전체코드

	public int solution1(int n) {
		
		int count = 0;
		
		for(int i = 1; i * i <= n; i++) {
			if(n % i == 0) {
				count += 2;
				
				if(i * i == n) {
					count--;
				}
			}
		}
		
		return count;
	}