각 자연수를 뒤집은 다음, 뒤집은 값이 소수일 때만 결과에 추가하면 됩니다. 숫자를 뒤집는 과정과 소수를 판별하는 과정을 분리하면 앞자리 0 처리와 판별 범위를 각각 확인하기 쉽습니다.
이 글의 목표는 숫자를 뒤집고 소수만 입력 순서대로 반환하는 함수를 작성하는 것입니다. 변수, 배열 또는 리스트, 반복문, 함수, 나머지 연산을 알고 있다고 가정합니다. 누적 프로젝트나 이전 회차의 코드는 필요하지 않습니다.
문제·입출력·제약
N개의 자연수가 주어집니다. 각 수의 십진수 자릿수를 거꾸로 읽어 정수로 만든 뒤, 그 값이 소수이면 출력합니다. 출력 순서는 입력 순서와 같습니다.
- 3 ≤ N ≤ 100
- 각 입력은 1 이상 100,000 이하의 자연수입니다.
- 뒤집은 결과의 앞자리 0은 정수로 바꾸면서 사라집니다. 예를 들어 910은 19, 20은 2가 됩니다.
- 같은 소수가 여러 번 나오면 각각 출력합니다. 정렬하거나 중복을 제거하지 않습니다.
원문 입력은 첫 줄에 N, 다음 줄에 N개의 자연수를 받습니다.
9
32 55 62 20 250 370 200 30 100예상 출력:
23 2 73 2 3아래 5언어 실습은 입력 파싱을 제외한 함수형 계약을 사용합니다. solution에 자연수 배열 또는 리스트를 전달하고, 뒤집은 소수 배열 또는 리스트를 반환합니다. 원문처럼 출력하려면 반환값을 공백으로 연결하면 됩니다. 해당하는 소수가 없으면 빈 결과를 반환합니다.
목차
직접 풀이와 5언어 실습
먼저 해답을 접어 둔 상태에서 다음 세 질문에 답해 보세요.
- 마지막 자릿수를 얻으려면 어떤 연산이 필요할까요?
- 지금까지 뒤집은 값의 오른쪽에 새 자릿수를 붙이려면 어떻게 계산할까요?
- 소수 판별에서 어떤 범위까지 약수를 확인하면 충분할까요?
JavaScript, Python, Java, C++, C# 모두 같은 문제를 풉니다. 아래 프로필의 시작 코드는 반환 형식만 갖춘 빈 풀이입니다. 구현을 추가한 뒤 원문 예제와 경계값을 비교하세요. 언어별 전체 해답은 하단의 접힌 영역에 있습니다.
독립 실행 시에는 사용하는 언어의 실행 환경과 호출용 진입점이 필요합니다. Java는 Solution 클래스의 정적 메서드, C#은 Solution 클래스의 정적 메서드를 호출합니다. 이 글은 표준 입력을 읽는 실행 프로그램이 아니라 함수 단위 풀이를 제공합니다.
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
function isPrime(value) {
if (value < 2) return false;
for (let divisor = 2; divisor * divisor <= value; divisor++) {
if (value % divisor === 0) return false;
}
return true;
}
function solution(arr) {
const result = [];
for (const value of arr) {
let remaining = value;
let reversed = 0;
while (remaining > 0) {
reversed = reversed * 10 + remaining % 10;
remaining = Math.floor(remaining / 10);
}
if (isPrime(reversed)) result.push(reversed);
}
return result;
}solution(arr: number[]): number[]. 입력 배열을 변경하지 않고 뒤집은 소수를 순서대로 반환합니다. solution([32,55,62,20,250,370,200,30,100])의 예상 반환값은 [23,2,73,2,3]입니다.
나머지로 마지막 자릿수를 얻고 Math.floor로 정수 몫을 구합니다. 입력값은 remaining에 복사합니다. 2 미만을 제외하고 divisor의 제곱이 value 이하인 동안 나눠 봅니다.
def is_prime(value):
if value < 2:
return False
divisor = 2
while divisor * divisor <= value:
if value % divisor == 0:
return False
divisor += 1
return True
def solution(arr):
result = []
for value in arr:
remaining = value
reversed_value = 0
while remaining > 0:
reversed_value = reversed_value * 10 + remaining % 10
remaining //= 10
if is_prime(reversed_value):
result.append(reversed_value)
return resultsolution(arr: list[int]) -> list[int]. 입력 리스트를 변경하지 않고 뒤집은 소수를 순서대로 반환합니다. solution([32,55,62,20,250,370,200,30,100])의 예상 반환값은 [23,2,73,2,3]입니다.
%로 자릿수를 꺼내고 //로 정수 몫을 구합니다. 입력 리스트를 순회하면서 별도 변수만 줄입니다. 소수일 때 append하므로 순서와 중복이 보존됩니다.
import java.util.ArrayList;
import java.util.List;
class Solution {
private static boolean isPrime(int value) {
if (value < 2) return false;
for (int divisor = 2; divisor * divisor <= value; divisor++) {
if (value % divisor == 0) return false;
}
return true;
}
public static List<Integer> solution(int[] arr) {
List<Integer> result = new ArrayList<>();
for (int value : arr) {
int remaining = value;
int reversed = 0;
while (remaining > 0) {
reversed = reversed * 10 + remaining % 10;
remaining /= 10;
}
if (isPrime(reversed)) result.add(reversed);
}
return result;
}
}Solution.solution(int[] arr)는 List<Integer>를 반환합니다. 입력 배열은 변경하지 않습니다. new int[]{32,55,62,20,250,370,200,30,100}의 예상 결과는 [23,2,73,2,3]입니다.
양의 int끼리의 나눗셈으로 마지막 자릿수를 제거합니다. 결과 개수가 달라지므로 ArrayList에 모읍니다. 이 문제의 값 범위에서는 int와 divisor 제곱을 사용할 수 있습니다.
#include <vector>
bool isPrime(int value) {
if (value < 2) return false;
for (int divisor = 2; divisor * divisor <= value; ++divisor) {
if (value % divisor == 0) return false;
}
return true;
}
std::vector<int> solution(const std::vector<int>& arr) {
std::vector<int> result;
for (int value : arr) {
int remaining = value;
int reversed = 0;
while (remaining > 0) {
reversed = reversed * 10 + remaining % 10;
remaining /= 10;
}
if (isPrime(reversed)) result.push_back(reversed);
}
return result;
}solution(const std::vector<int>& arr)는 std::vector<int>를 반환합니다. 입력은 변경하지 않습니다. {32,55,62,20,250,370,200,30,100}의 예상 결과는 {23,2,73,2,3}입니다.
입력 벡터는 const 참조로 받습니다. 정수 나눗셈으로 자릿수를 제거하고 push_back으로 결과를 쌓습니다. 별도의 정렬이나 집합은 사용하지 않습니다.
using System.Collections.Generic;
public class Solution {
private static bool IsPrime(int value) {
if (value < 2) return false;
for (int divisor = 2; divisor * divisor <= value; divisor++) {
if (value % divisor == 0) return false;
}
return true;
}
public static List<int> solution(int[] arr) {
List<int> result = new List<int>();
foreach (int value in arr) {
int remaining = value;
int reversed = 0;
while (remaining > 0) {
reversed = reversed * 10 + remaining % 10;
remaining /= 10;
}
if (IsPrime(reversed)) result.Add(reversed);
}
return result;
}
}Solution.solution(int[] arr)는 List<int>를 반환합니다. 입력 배열은 변경하지 않습니다. new int[] {32,55,62,20,250,370,200,30,100}의 예상 결과는 [23,2,73,2,3]입니다.
foreach에서 받은 값을 remaining에 복사하여 입력을 보존합니다. 정수 나눗셈과 나머지로 뒤집고, 소수인 값만 List에 추가합니다.
접근 과정
1. 마지막 자릿수부터 꺼내기
자연수의 마지막 자릿수는 remaining % 10입니다. 그 자릿수를 제거하려면 10으로 나눈 정수 몫을 구합니다. 예를 들어 370에서 0을 꺼내면 37, 다시 7을 꺼내면 3, 마지막으로 3을 꺼내면 0이 됩니다.
뒤집은 값은 0에서 시작합니다. 자릿수를 하나 꺼낼 때마다 reversed = reversed * 10 + digit으로 갱신합니다. 370의 경우 뒤집은 값은 0 → 0 → 7 → 73이 됩니다. 처음 꺼낸 0은 값의 크기를 늘리지 않으므로 앞자리 0이 자연스럽게 사라집니다.
반복 중에는 뒤집은 값에 이미 꺼낸 자릿수가 순서대로 쌓이고, 남은 값에는 아직 처리하지 않은 자릿수가 있습니다. 남은 값이 0이 되면 모든 자릿수를 처리한 것입니다.
2. 뒤집은 값이 소수인지 확인하기
소수는 1보다 큰 정수 중 양의 약수가 1과 자기 자신뿐인 수입니다. 따라서 2 미만은 먼저 제외합니다. 이후 2부터 약수를 찾아 하나라도 나누어떨어지면 소수가 아닙니다.
검사 조건은 divisor * divisor <= value입니다. 합성수의 약수 쌍 중에는 반드시 제곱근 이하의 약수가 하나 이상 있습니다. 두 약수가 모두 제곱근보다 크면 곱이 원래 수보다 커지기 때문입니다. 등호를 포함해야 49를 7로 나누어 확인할 수 있습니다.
2는 첫 검사 조건인 4 ≤ 2가 거짓이므로 반복문에 들어가지 않고 소수로 판별됩니다. 별도의 예외 분기를 추가할 필요가 없습니다.
3. 입력 순서대로 결과에 추가하기
각 입력에 대해 뒤집기와 소수 판별을 마친 뒤, 소수인 값만 결과 배열 끝에 추가합니다. 이렇게 하면 입력 순서와 중복이 그대로 유지됩니다. 원래 수가 소수인지 먼저 검사하면 안 됩니다. 예를 들어 32는 합성수지만 뒤집은 23은 소수입니다.
예제 추적
| 입력 | 뒤집은 정수 | 판별 근거 | 결과에 추가 |
|---|---|---|---|
| 32 | 23 | 2, 3, 4로 나누어떨어지지 않음 | 23 |
| 55 | 55 | 5의 배수 | 제외 |
| 62 | 26 | 2의 배수 | 제외 |
| 20 | 2 | 소수 | 2 |
| 250 | 52 | 2의 배수 | 제외 |
| 370 | 73 | 2부터 8까지 약수가 없음 | 73 |
| 200 | 2 | 소수, 앞서 나온 2도 유지 | 2 |
| 30 | 3 | 소수 | 3 |
| 100 | 1 | 2 미만 | 제외 |
따라서 예상 반환값은 [23, 2, 73, 2, 3]입니다. 다음 호출은 JavaScript 풀이 뒤에 붙이는 부분 코드입니다.
const values = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log(solution(values).join(' '));예상 콘솔 출력은 23 2 73 2 3입니다. 이 결과는 원문 예제와 알고리즘을 대조한 기대값이며, 이 작성 회차에서 실행한 로그는 아닙니다.
경계값과 복잡도
[1, 10, 100000]→[]: 모두 뒤집으면 1입니다.[20, 200, 2]→[2, 2, 2]: 0 제거와 중복 보존을 함께 확인합니다.[94, 121, 32]→[23]: 49와 121은 완전제곱수이므로 제외합니다.[910, 370, 30]→[19, 73, 3]: 끝자리 0이 있는 수를 확인합니다.[23, 13, 17]→[31, 71]: 원래 수가 소수여도 뒤집은 32는 제외합니다.
입력 개수를 N, 최대 자릿수를 D, 뒤집은 값의 최댓값을 M이라고 하면 자릿수 뒤집기는 수마다 O(D), 소수 판별은 최악에 O(√M)입니다. 전체 시간 복잡도는 O(N(D + √M))입니다. 주어진 입력 범위에서 D는 최대 6이며, 뒤집은 값은 100,000보다 작습니다.
반환되는 소수의 개수를 K라고 하면 결과 저장 공간은 O(K)입니다. 결과를 제외한 추가 공간은 O(1)입니다. 이 범위에서는 Java와 C#의 int 및 C++의 일반적인 32비트 int에서 뒤집기 연산과 판별 중 제곱 계산이 안전한 범위에 있습니다. 더 큰 정수로 문제를 확장하면 자료형과 곱셈 범위를 다시 검토해야 합니다.
해답·해설 보기
5언어 전체 풀이 코드와 해설 펼치기
아래 코드는 각 언어의 함수 풀이 전체입니다. 표준 입력 파서와 호출용 main 진입점은 포함하지 않습니다. 복사할 때는 사용할 언어의 코드 블록 하나를 선택하세요. 다음 경로는 풀이를 저장할 파일명입니다.
JavaScript — solution.js
JavaScript의 일반 나눗셈은 소수 부분을 남기므로 Math.floor로 정수 몫을 구합니다. 입력은 양수이므로 내림 연산으로 마지막 자릿수를 제거할 수 있습니다.
Python — solution.py
def is_prime(value):
if value < 2:
return False
divisor = 2
while divisor * divisor <= value:
if value % divisor == 0:
return False
divisor += 1
return True
def solution(arr):
result = []
for value in arr:
remaining = value
reversed_value = 0
while remaining > 0:
reversed_value = reversed_value * 10 + remaining % 10
remaining //= 10
if is_prime(reversed_value):
result.append(reversed_value)
return resultPython은 //로 정수 몫을 구합니다. 뒤집기와 소수 판별을 별도 단계로 유지하고 소수인 값만 결과 리스트에 추가합니다.
Java — Solution.java
Java의 정수 나눗셈으로 자릿수를 제거합니다. 반환 개수가 입력에 따라 달라지므로 결과는 List<Integer>로 반환합니다.
C++ — solution.cpp
C++은 입력을 const 참조로 받으며 결과는 별도 벡터에 저장합니다. 입력 배열을 정렬하거나 수정할 필요가 없습니다.
C# — Solution.cs
C#도 정수 몫과 나머지를 사용합니다. 다섯 풀이 모두 2 미만 제외, 제곱근 경계 포함, 입력 순서와 중복 보존이라는 같은 조건을 구현합니다.
자가 확인
- 370을 뒤집는 동안 남은 값과 뒤집은 값이 어떻게 변하는지 한 단계씩 적어 보세요.
- 소수 판별 조건에서 등호를 빼면 49가 왜 잘못 판별되는지 설명해 보세요.
- 원래 입력이 소수인지 먼저 검사하면 32를 처리할 때 어떤 오류가 생기나요?
- 결과를 집합으로 바꾸면
[20, 200, 2]의 요구사항을 왜 만족하지 못하나요?
작은 변형 과제: 뒤집은 소수만 반환하는 대신 각 입력과 뒤집은 소수의 쌍을 반환해 보세요. [32, 20, 55]의 예상 결과는 [[32, 23], [20, 2]]입니다. 소수 판별 함수는 그대로 두고 결과에 추가하는 값만 바꿀 수 있는지 확인하세요.
출처와 확인 범위
문제 조건과 원문 예제는 제공된 PDF의 2쪽을 기준으로 했습니다. 원본 TXT에는 산술 방식과 문자열 방식의 JavaScript 풀이가 함께 들어 있으며, 이 글은 산술 방식으로 설명합니다. 원본의 num === 1 제외 조건은 소수 정의를 분명히 드러내도록 value < 2로 확장했습니다.
- 원문 식별자:
s04-p02, 섹션 4의 2번 문제 「뒤집은 소수」. - PDF:
알고리즘/섹션4/섹션 4. 완전탐색(블루투포스).pdf, 2쪽. 제공된 SHA-256:991866da4b0deea3078cdd24e5ee3e792633fee7f3cffc90a92ae8a94bb6607d. - TXT:
알고리즘/섹션4/2. 뒤집은 소수.txt. 제공된 SHA-256:9cc8f3bec5ccd659d4df3bb8f9fe9bb49936a3701610105bd513fea15626da82. - 식별 정보: 위에 기재한 파일명과 전달된 SHA-256. 원본 파일을 직접 열거나 해시를 다시 계산한 것은 아니며, 전달된 추출문과 식별 정보를 사용했습니다.
- 작성 기준:
Ruleset 1.11 / TPL-05 1.7. 설명 기준: 제공된 문제 원문과 예시.
검증 상태: 5언어 코드 실행·컴파일, 저장 후 프로필 복원과 코드 복사, 편집기·언어 전환·힌트·비교 기능, PC·320px·400px 화면, 공개 URL 및 학습 경로는 미확인입니다. 본문의 실행 결과는 예상 결과입니다. 제공된 자료에는 공개 학습 목록, 개념 글의 WP ID·URL, 현재 학습 해시가 없어 선수 글과 권장 다음 1편을 확정하지 않았습니다. 대표 이미지, 실제 내부 링크, 저장 후 감사와 공개 검수의 보완이 필요하며 발행 또는 전체 완료를 뜻하지 않습니다.
이 문제에 쓰인 개념
- 나머지와 정수 나눗셈: 마지막 자릿수를 얻고 제거하는 원리를 이해하면 숫자 뒤집기를 직접 구현할 수 있습니다.
- 배열 순회와 조건부 수집: 각 입력을 한 번씩 처리하면서 순서와 중복을 보존하는 이유를 설명할 수 있습니다.
- 소수 판별과 반복문의 경계: 2 미만 제외와 제곱근까지의 약수 검사를 통해 1과 완전제곱수를 올바르게 처리할 수 있습니다.
관련 공개 개념 글 2~3편의 링크는 미확인입니다. 실제 공개 제목·URL·게시 상태를 확인한 뒤 각 항목에 연결해야 합니다. 현재 공개 권장 경로의 다음 글도 확인되지 않아 추정 링크를 넣지 않았습니다.
관련 학습: 자릿수의 합: 동률이면 더 큰 수 고르기
이 글이 도움이 되었나요?
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
