문제
내가 생각했을때 문제에서 원하는부분
입력은 여러 개의 테스트 케이스로 이루어져 있다.
테스트 케이스의 개수는 1,000개를 넘지 않는다.
각 테스트 케이스는 길이가 255를 넘지 않는 숫자 문자열로 이루어져 있다.
입력의 마지막 줄에는 0이 하나 주어진다.
소수 부분 문자열이 최소 하나 이상 존재하는 입력만 주어진다.
각 테스트 케이스에 대해서, 가장 큰 소수 부분 문자열을 출력한다.내가 이 문제를 보고 생각해본 부분
static boolean[] isPrime 선언 및 초기화
isPrime 배열은 1부터 100,000까지의 숫자 중 어떤 숫자가 소수인지 아닌지를 저장하는 용도이다.
boolean 타입이라서 true면 소수, false면 소수가 아님을 나타낸다.
static으로 선언하여 프로그램 시작 시 한 번만 생성되고, 모든 인스턴스에서 공유되며, main 메서드에서도 바로 접근할 수 있도록 했다.
이렇게 미리 소수를 계산해두면 매번 소수를 판별하는 시간을 줄일 수 있어 효율적이다.
main 메서드 시작 및 BufferedReader 설정
자바 프로그램의 시작점인 main 메서드이다.
BufferedReader는 대량의 입력을 효율적으로 처리하기 위해 사용한다.
System.in은 표준 입력(콘솔)을 의미하고, InputStreamReader를 통해 바이트 스트림을 문자 스트림으로 변환하여 BufferedReader가 읽을 수 있도록 한다.
throws IOException는 입출력 과정에서 발생할 수 있는 예외(예: 파일을 읽을 수 없는 경우)를 현재 메서드를 호출한 곳으로 미룬다는 의미이다.
에라토스테네스의 체 (소수 미리 계산하기)
이 부분은 isPrime 배열을 채우는 과정으로, '에라토스테네스의 체'라는 유명한 소수 판별 알고리즘을 사용한다.
먼저 0과 1을 제외한 모든 수를 소수(true)라고 가정한다.
그다음 2부터 시작해서, 현재 수가 소수라면 그 수의 배수들을 모두 소수가 아니라고(false) 표시한다.
예를 들어, p = 2일 때 isPrime[2]가 true이므로, 4, 6, 8, ...을 false로 만든다.
p = 3일 때 isPrime[3]이 true이므로, 9, 12, 15, ...를 false로 만든다. (여기서 p * p부터 시작하는 이유는 2 * 3 = 6과 같은 작은 배수들은 이미 2에서 처리되었기 때문이다.
p까지의 배수들은 p보다 작은 소수들의 배수로 이미 제거되어 있다.)
이 과정을 100,000의 제곱근(약 316)까지만 반복하면 100,000까지의 모든 소수를 효율적으로 판별할 수 있다.
프로그램 실행 초기에 한 번만 계산하므로, 각 테스트 케이스를 처리할 때는 소수 여부만 빠르게 확인할 수 있다.
테스트 케이스 반복 처리
while(true) 무한 루프를 사용하여 문제에서 요구하는 여러 개의 테스트 케이스를 처리한다.
br.readLine()을 통해 한 줄의 숫자 문자열을 입력받는다.
만약 입력받은 문자열이 "0"과 같다면, 문제의 종료 조건에 따라 break 문으로 루프를 빠져나와 프로그램을 종료한다.
가장 큰 소수 찾기 (maxPrimeFound)
maxPrimeFound = 0;: 각 테스트 케이스가 시작될 때마다, 현재 케이스에서 찾을 가장 큰 소수를 저장할 변수를 초기화한다.
이중 for 루프 (i, j):
바깥쪽 for 루프는 부분 문자열의 시작 인덱스 i를 0부터 str.length() - 1까지 반복한다.
안쪽 for 루프는 부분 문자열의 끝 인덱스 j를 i부터 str.length() - 1까지 반복한다.
이 두 루프를 통해 문자열 str에서 만들 수 있는 모든 가능한 부분 문자열(substring)을 생성한다.
길이 최적화 (if (j - i + 1 > 6)):
부분 문자열의 길이가 6자리를 초과하면(j - i + 1은 부분 문자열의 길이), 해당 숫자는 최소 100,000(6자리)을 넘어가게 된다.
문제 조건상 100,000 이하의 소수만 유효하므로, 더 이상 이 부분 문자열은 검사할 필요가 없다.
break를 사용하여 안쪽 루프를 종료하고 다음 시작 인덱스 i로 넘어간다.
이는 불필요한 연산을 줄여 코드 실행 시간을 단축시키는 중요한 최적화이다.
부분 문자열 추출 (str.substring(i, j + 1)): substring 메서드를 사용하여 i부터 j까지의 부분 문자열을 추출한다. (참고로 substring의 두 번째 인자는 exclusive이다.)
"0"으로 시작하는 다자리 숫자 처리 (if (sub.length() > 1 && sub.charAt(0) == '0')):
만약 추출된 부분 문자열의 길이가 1보다 크고, 첫 글자가 '0'이라면, 이는 "01", "007"과 같이 실제 숫자로는 유효하지 않은 형태(일반적으로 선행 0이 없는 형태)이므로 continue를 통해 다음 부분 문자열로 넘어간다. (예: "0" 그 자체는 한 자리 숫자이므로 제외되지 않다. "0"은 소수가 아니다.)
숫자 변환 및 범위 확인:
Integer.parseInt(sub)를 사용하여 부분 문자열을 실제 int형 숫자로 변환한다.
변환된 num이 100,000보다 크다면, 이는 문제의 소수 범위(<= 100000)를 벗어나므로 continue로 다음 부분 문자열을 검사한다.
소수 여부 확인 및 maxPrimeFound 갱신:
if (isPrime[num])를 통해 미리 계산해둔 isPrime 배열에서 num이 소수인지 빠르게 확인한다.
num이 소수이고, 현재까지 찾은 maxPrimeFound보다 크다면, maxPrimeFound = num을 통해 최댓값을 갱신한다.
결과 출력: 모든 부분 문자열을 탐색한 후, 최종 maxPrimeFound 값을 System.out.println()으로 출력한다.
BufferedReader 닫기
마지막으로, 사용한 BufferedReader 자원을 해제한다.코드로 구현
package baekjoon.baekjoon_31;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
// 백준 5636번 문제
public class Main1245 {
// 100,000까지의 소수를 미리 저장할 배열
static boolean[] isPrime = new boolean[100001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 에라토스테네스의 체를 사용하여 100,000까지의 소수를 미리 계산합니다.
// isPrime 배열을 true로 초기화하여 모든 숫자가 소수라고 가정합니다.
Arrays.fill(isPrime, true);
// 0과 1은 소수가 아니므로 false로 설정합니다.
isPrime[0] = isPrime[1] = false;
// 2부터 시작하여 숫자의 제곱근까지 반복합니다.
for (int p = 2; p * p <= 100000; p++) {
// 현재 숫자가 소수(true)인 경우, 해당 숫자의 배수들을 소수가 아니라고 표시합니다.
if (isPrime[p]) {
for (int i = p * p; i <= 100000; i += p)
isPrime[i] = false;
}
}
// 입력의 마지막 줄에 0이 주어질 때까지 반복하여 테스트 케이스를 처리합니다.
while (true) {
String str = br.readLine();
// 입력이 "0"이면 반복을 종료합니다.
if (str.equals("0")) {
break;
}
int maxPrimeFound = 0; // 현재 테스트 케이스에서 찾은 가장 큰 소수를 저장할 변수
// 모든 가능한 부분 문자열을 탐색합니다.
// i는 부분 문자열의 시작 인덱스
for (int i = 0; i < str.length(); i++) {
// j는 부분 문자열의 끝 인덱스
for (int j = i; j < str.length(); j++) {
// 부분 문자열이 6자리를 초과하면 100,000보다 커질 가능성이 높으므로 더 이상 확인하지 않습니다.
// (100,000은 6자리 숫자입니다.)
if (j - i + 1 > 6) {
break;
}
// 부분 문자열을 추출합니다.
String sub = str.substring(i, j + 1);
// 추출한 부분 문자열이 숫자로 시작하는지 (즉, '0'이 아닌지) 확인합니다.
// 단, '0'이 한자리 숫자인 경우는 제외합니다 (예: "0"은 소수가 아닙니다).
// "0123" 같은 경우를 123으로 인식하는 건 괜찮지만, "0" 자체는 숫자 0이므로 소수가 아닙니다.
if (sub.length() > 1 && sub.charAt(0) == '0') {
continue; // 여러 자리 숫자가 '0'으로 시작하면 유효하지 않은 것으로 간주하고 건너뜁니다.
}
int num = Integer.parseInt(sub); // 부분 문자열을 정수로 변환합니다.
// 숫자가 100,000보다 크면 우리가 찾는 소수 범위 밖이므로 건너뜁니다.
if (num > 100000) {
continue;
}
// 변환된 숫자가 소수인지 확인하고, 현재까지 찾은 가장 큰 소수보다 크면 갱신합니다.
if (isPrime[num]) {
if (num > maxPrimeFound) {
maxPrimeFound = num;
}
}
}
}
// 현재 테스트 케이스의 가장 큰 소수를 출력합니다.
System.out.println(maxPrimeFound);
}
br.close(); // BufferedReader를 닫습니다.
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer