[백준] 15663. N과 M (9)

백준 문제 풀이

 

[백준] 15663. N과 M(9)

15663번: N과 M (9)

 

---

문제 해석

15654. N과 M(5) 문제와 비슷한 문제이다. 역시 브루트 포스를 통해 해결했다.
다른 점은 예제의 입력을 보면 15654번 문제와 다르게 주어진 자연수가 중복된 숫자가 올 수 있다는 것. 즉 1824 이런 숫자만 주어지는 것이 아닌 1118 이렇게 1이 여러 번 있는 자연수의 입력도 주어질 수 있다는 것이다.

출력의 조건을 보면 중복되는 수열을 여러 번 출력하면 안 된다. 그러므로 N과 M(5) 문제 풀이를 그대로 쓰기에는 무리가 있고, 여기에 중복을 제거할 수 있는 조건을 추가해 주어야 한다.

 

풀이

int numbers[8];			// 입력을 주어진 수를 저장할 배열
int result[8];			// 결과로 출력할 수를 저장할 배열
bool is_used[9];		// numbers에서 i번째에 있는 수를 사용했는지 여부
int using_num[9];		// 같은 숫자 재사용을 막기 위한 배열

void PrintResult(int length_of_result) {
	// 만들어진 result를 length_of_result에 맞추어 출력해주는 함수

	for (int i = 0; i < length_of_result; i++)
	{
		cout << result[i] << " ";
	}
	cout << "\n";

	return;
}

void FillArray(int cur_index, int num_limit, int length_limit) {
	// result 배열에 알맞는 값을 집어넣는 함수

	if (cur_index == length_limit) {
		// 현재 길이가 원하는 길이(m)일 때, 출력해줌
		PrintResult(length_limit);
		return;
	}

	for (int i = 0; i < num_limit; i++)
	{
		int current_num = numbers[i];		// numbers에서 하나씩 가져오면서 판단

		if (!is_used[i]) {
			if (using_num[cur_index] != current_num) {
				using_num[cur_index] = current_num;
				result[cur_index] = current_num;
				is_used[i] = true;
				FillArray(cur_index + 1, num_limit, length_limit);
				is_used[i] = false;
			}
		}
	}
	using_num[cur_index] = 0;
}

//	sort(numbers, numbers + n);
// 	FillArray(0, n, m);

이전 N과 M문제와 마찬가지로, 정렬을 해 주고 시작한다. 그 후 FillArray함수를 통해 결과 배열의 각 자릿수를 재귀적으로 채워 준다. FillArray함수는 현재 길이(cur_index)가 목표한 길이(length_limit) 일때 PrintResult 함수를 통해 출력하도록 해 두었다.

그리고 입력받은 수의 배열을 차례로 for문을 통해 탐색하면서 아직 사용되지 않은 숫자일 경우 배열에 넣고 다시 FillArray함수를 수행하도록 했는데, 여기서 N과 M(5) 문제와 다르게 중복 검사를 위해 추가된 점이 있다.

N과 M(5)에서의 풀이

N과 M(9)에서의 풀이

using_num배열을 전역 변수로 추가했는데, 해당 배열은 i번째 자리에 올 숫자들을 임시로 저장해둘 배열이다. 예를 들면 입력으로

6 2
1 1 2 2 3 3

이 주어졌다고 하면, 1 2가 두 번 이상 출력되면 안 될 것이다. 따라서 배열을 만들어주는 for문 부분에서 1 다음에 2 자리(index는 1)에 한번 2가 들어가게 된다면 using_num[1]에 2를 저장해 둔다.

이제 출력이 끝나고, 두 번째 2가 index가 1인 곳에 들어가기 전에 using_num[1]를 살펴보면 2가 들어있는 것을 알 수 있다. 현재 for문 반복을 돌면서 같은 index에 이미 같은 숫자가 들어갔던 것을 알 수 있으니 이 경우는 넘어가게 된다.

 

마지막으로 해당 index에서 for문이 끝나면 using_num[i]를 0으로 초기화 해 주어야 한다. 그렇지 않는다면

3 3
9 9 8

과 같은 사례에서 오류가 난다.

8 9 9를 출력하고 9 8 9를 출력할 때 이미 using_num[2]에 9가 들어가 있기 때문에 넘어가게 되기 때문!

 

전체 소스코드 (Github)