알고리즘 문제 7. 중복없는 랜덤값 구하기

1. 로또 번호 생성기를 구현 하시오.
   A. 최대 번호값과 생성 숫자 개수를 입력하면 해당 조건 내에서 중복되지 않는 숫자를 출력하는 로또 번호 생성기를 구현.
   B. 최대값 : 60, 생성숫자 : 10 을 입력하면 1 ~ 60 사이의 중복되지 않는 숫자 10개를 생성한다.

내 풀이 )

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
void loto(int max, int count)
{
	srand(time(NULL));

	int lotoNum[10000];

	//10개 출력함
	for (int i = 0; i < count; i++)
	{
		int randNum = rand() % max + 1;

		
		int search = 0;
		while (1) 
		{
			int search = 0;
			for (int j = 0; j < i; j++)
			{
				if (lotoNum[j] == randNum)
				{
					search = 1;
					randNum = rand() % max + 1;
				}
			}

			if (search == 0) {
				break;
			}
		}


		lotoNum[i] = randNum;
	}


	for (int k = 0; k < count; k++)
	{
		printf("%d ", lotoNum[k]);
	}

}

int main()
{

	int max = 0;
	int count = 0;

	scanf("%d %d", &max, &count);

	loto(max, count);

	return 0;
}

문제점 : 동적 메모리 할당을 하지 않았으며, 시간 복잡도가 올라가는 문제가 있음. 이를 해결하기 위해 임의의 변수 isUsed를 선언하여 do while문으로 문제를 푼다.

#include <iostream>

using namespace std;

int main() {

	//입력 : 최대 번호값과 생성 숫자 개수를 입력 받는다.
	cout << "최대 번호 값을 입력하세요 : ";
	int maxValue;
	cin >> maxValue;
	
	cout << "생성할 숫자의 개수를 입력하세요. : ";
	int digitCount;
	cin >> digitCount;

	//처리 : 로또 생성
	// 1 ~ maxValue 사이의 값중 중복되지 않게 digitCount만큼 뽑음
	int* lotto = new int[digitCount];
	
	//로또 번호 정하기
	//1. [1 - maxValue]사이의 값으로 무작위로 뽑는다. 뽑은 값을 N이라 한다.
	//2. 중복인지 확인한다.
	//2-1,. 중복이면? 1번을 다시 수행한다.
	//2-2. 중복이 아니면 데이터를 저장한다.
	//3. 1번부터 digitCount만큼 반복한다.

	srand(time(NULL));

	for (int i = 0; i < digitCount; i++)
	{
		int N = 0;
		
		bool isExist = false;
		do
		{		
			N = rand() % maxValue + 1;
			
			for (int j = 0; j < i; j++)
			{	
				if (N == lotto[j]) {
					isExist = true;
					break;
				}
			}

		} while (isExist);


		lotto[i] = N;
	}



	//출력 : 로또 번호 출력
	for (int i = 0; i < digitCount; i++)
	{
		cout << lotto[i] << " ";
	}


	delete[] lotto;

	return 0;
}