[백준 15651] N과 M(3)

🫡문제

백준 15651 - N과 M(3)

🫡코드

import java.util.Scanner;

//N과 M(3) - 완전탐색
public class Main {

	static int N, M;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		arr = new int[M];

		// 1번째 요소부터 탐색
		Search(0);

		System.out.print(sb.toString());
	}

	static void Search(int i) {
		if (i == M) { // 모든 숫자를 다 탐색했을 경우
			for (int k = 0; k < M; k++) {
				sb.append(arr[k]).append(" ");
			}
			sb.append("\n");
		} else {
			for (int n = 1; n <= N; n++) {
				arr[i] = n;
				Search(i + 1);
				arr[i] = 0;
			}
		}

	}

}

🫡풀이

완전탐색

N개의 숫자 중 중복을 허용해서 M개를 순서있게(오름차순) 으로 나열하는 문제

• 모든 숫자를 모든 공간에 한번씩 다 사용 가능
  시간복잡도 : O(N^M)
  공간복잡도 : O(M)

1. 먼저 M 크기의 배열을 선언해준다.
2. 가장 첫번째 숫자부터 탐색 하기 위한 함수 선언
3. 탐색
   3.1. M개의 숫자 만큼 탐색했을 경우 해당 배열 출력
   3.2. 계속 숫자를 탐색해야하는 경우 배열의 가장 첫번째 자리에 1부터 숫자를 넣어준다.
   3.2.1. 재귀함수를 통해 현재 탐색중인 숫자보다 1 큰 수를 넣어 계속 탐색해준다.
   3.2.2. 해당 숫자의 탐색이 끝나면 다시 사용할 수 있도록 배열을 0으로 초기화 해준다.

💡시간초과
Scanner만 사용하여 for문 안에서 모든 숫자를 다 탐색했을 경우 System.out.println으로 계속해서 출력해주었더니 시간초과가 발생했다.

시간초과 문제를 해결하기 위해 StringBuilder를 사용하였다.
String과 문자열을 더할 때 새로운 객체를 만들지 않고 기존 데이터에 append()를 사용하여 더해주어 시간초과를 방지할 수 있었다.