inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

14. 뒤집은 소수

에라토스테네스의 체를 활용한 isPrime 함수

430

Bonnate

작성한 질문수 4

1

선생님 소수와 관련된 문제라 에라토스테네스의 체 알고리즘을 이용하여 배열에 미리 소수에 대한 여부를 파악하여 저장해두었습니다. isPrime 함수는 단순히 해당 배열의 값이 true인지 false인지 리턴을 하는것이라, 함수 자체의 의미가 없어지는거 같은 느낌이 들어서요.

 

실제 코딩테스트에도 이와같이 작성해도 문제가 없을까요? 아니면 함수의 의미에 맞게 함수 내부적으로 연산을 수행해야 할까요?

 

#include <iostream>

bool isPrime(int x);
int reverse(int x);

// 에라토스테네스의 체 알고리즘
static bool primes[100001];

int main()
{
	int N, numInput;
	scanf_s("%d", &N);

	// 모두 true로 초기화
	for (int i = 0; i < 100001; ++i)
		primes[i] = 1;

	// 0과 1은 소수가 아님
	primes[0] = primes[1] = false;

	// 에라토스테네스의 체 알고리즘을 통해 모든 소수 판별
	for (int i = 2; i <= std::sqrt(100001); ++i)
	{
		if (!primes[i])
			continue;

		primes[i] = true;
		for (int j = i * 2; j < 100001; j += i)
			primes[j] = false;
	}

	// 나머지 계산
	for (int i = 0; i < N; ++i)
	{
		scanf_s("%d", &numInput);

		int reverseNum = reverse(numInput);
		if (isPrime(reverseNum))
			printf("%d ", reverseNum);
	}
}

bool isPrime(int x)
{
	return primes[x];
}

int reverse(int x)
{
	int num = 0;

	while (x > 0)
	{
		num = num * 10 + x % 10;
		x /= 10;
	}

	return num;
}

c++ 코딩-테스트

답변 1

1

김태원

안녕하세요^^

이 문제에서는 N제한이 100까지이지만 실제 코딩테스트에서 N제한이 많이 커진다면 위에 코드가 영상의 방법보다 더 효율적인 코드라 생각됩니다. 잘 하셨습니다.

0

Bonnate

감사합니다 !!

87번 채점 프로그램에 오류가 있는 것 같습니다.

0

89

2

그리디 파트

0

115

2

안녕하세요. 선생님(54번 코드 관련 문의)

0

141

2

테스트 파일 exit_coe_1, time_limit_exceeded 질문

0

143

1

C언어로 코드를 짜면 채점 시에 한 문제 빼고 시간 초과가 발생하는데 해결하는 방법이 있을까요?

0

172

1

19번 질문있습니다

0

123

1

6번 관련 채점오류입니다

0

88

2

22번 문제는 C로 풀어주신 건가요 C++로 풀어주신 건가요?

0

166

2

dev C++ 콘솔창 바로 닫힘

0

245

1

최신화하기

0

171

1

채점이 안되요...

1

261

1

안녕하세요 강사님 정렬에 대해서 설명이 조금 더 듣고 싶습니다.

0

113

1

45번 공주구하기 문제를 list를 이용해서 이렇게 풀어도 될까요?

0

155

1

39번 두 배열 합치기 문제 채점 오류인가 코드 오류인가

0

155

0

채점기에서 틀렸다고 나오는데 이유를 모르겠습니다.

0

149

2

해당 강의에서 C언어로만 진행하는 강의 문의 건

0

145

2

87번 문제 섬나라 아일랜드 질문

0

128

1

16번 문제에서 직접 답을 대입하면 정답이 나오는데 채점에서 wrong answer가 나옵니다.

0

149

1

40번 교집합 문제

0

166

1

43번 뮤직비디오 문제 테스트케이스 4번을 만족 못합니다.

0

170

1

41. 연속된 자연수의 합 문제 질문있습니다.

0

166

1

질문있습니다.

0

193

2

시간초과가 나요

0

172

1

43번 문제 3 ~ 5번에 문제가 있는것 같습니다.

0

249

1