백준 10448 소인수 분해 (JAVA 자바 풀이)

백준 11653 소인수 분해 (JAVA 자바 풀이)

 

---

 

---

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(bufferedReader.readLine());

		int[] triNumbers = new int[1000];
		int n =0;
		int triCount =0;
		do {
			n++;
			triNumbers[n] = n * (n + 1) / 2;
			triCount++;
		} while (triNumbers[n] < 998);

		boolean[] triNumbersSum = new boolean[1001];
		createSummationMap(triNumbers, triCount, triNumbersSum);

		StringBuilder stringBuilder = new StringBuilder();
		while (N-->0){
			int answer = triNumbersSum[Integer.parseInt(bufferedReader.readLine())] ? 1: 0;
			stringBuilder.append(answer).append("\n");
		}

		System.out.print(stringBuilder);
	}

	private static void createSummationMap(int[] triNumbers, int triCount, boolean[] triNumbersSum) {
		for (int i = 1; i<= triCount; i++){
			for (int j = i; j<= triCount; j++){
				for (int k = j; k<= triCount; k++){
					int sum = triNumbers[i] + triNumbers[j] + triNumbers[k];
					if (sum >=1001){
						continue;
					}
					triNumbersSum[sum] = true;
				}
			}
		}
	}
}

 

 

완전 탐색으로 푼다. 

 

카운팅 배열의 원리가 적용된 boolean 배열을 이용했다.

 

createSummationMap() 메서드는 세 개의 삼각수를 선택하여 합을 계산하고, 계산된 합이 1001 이하인 경우 triNumbersSum 배열의 해당 인덱스를 true로 설정한다. 이 메서드는 모든 가능한 조합의 합을 계산하고 마크하므로 brute force 방식의 알고리즘이다.

세 개의 삼각수를 선택하여 합한 결과가 1001 이하인지 여부를 판단해야 할 때 위에서 만든 boolean 배열을 사용한다. 조건에 맞다면, 즉 삼각수 3개의 합으로 구할 수 있는 자연수라면, 배열에 true로 기록되어 있을 것이므로 1을 표기하고 그렇지 않으면 0을 표기한다.

 

이렇게 표기한 값을 Stringbuilder 객체로 만들어 저장하고, 마지막에 출력한다. 

 

 

시간 복잡도는 다음과 같다. 

i) N을 입력받는 부분: 시간 복잡도: O(1)

ii) do-while 루프: 
- triNumbers 배열을 채우는 루프
- 최대 1000번 반복
- 시간 복잡도: O(1)

 

iii) createSummationMap 메서드:

- 세 개의 중첩된 for 루프
- 각 루프는 triCount까지 반복
- 중첩된 루프이므로 시간 복잡도: O(triCount^3)

 

iV) while 루프:
- N번 반복
- 시간 복잡도: O(N)

 

따라서, 주어진 코드의 전체 시간 복잡도는 다음과 같다.

O(1) + O(1) + O(triCount^3) + O(N)

그러나 triCount는 1000 이하의 값에서 실제 계산시 44로 확인된다.

따라서 triCount^3은 약 9만으로 크지 않은 숫자이다.

 

따라서 주어진 코드의 시간 복잡도는 O(N)이 될텐데 문제에서 N의 값의 범위는 주어지지 않은 듯하다.