Step 9-1번 문제는 어제 풀었으므로 오늘은 생략.
Step 9-2번 문제(2581번).
**풀이에 참고한 블로그**
[백준] 2581번 : 소수 - JAVA [자바] (tistory.com)
[백준] 2581번 : 소수 - JAVA [자바]
https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는
st-lab.tistory.com
중요1) 예제 데이터에서 원하는 출력이 나왔다고 되는 게 아니다. 백준 알고리즘은 아주아주 다양한 데이터를 내가 만든 알고리즘에 다 넣고, 이 데이터에서 모두 오류 없이 정확한 출력이 나왔을 때만 정답으로 인정한다.
=> 내가 모르는 다양한 입/출력 예시가 있고 그에 따른 실행 예외가 발생할 수 있으니 많은 것을 고려해야 한다...
하지만 나는 도무지 뭐가 잘못된 건지도 예상할 수 없었으므로... 다른 사람의 풀이를 분석해 보자.
핵심은, 소수를 구하기 위해서 사용하는 에라토스테네스의 체 알고리즘이었다!
특정 범위 안의 소수를 구할 때 하나씩 지워 나가고 아닌 것만을 남기는 알고리즘이다.
이때 코드를 보기 단순화시키려고 main 메소드의 밖에다가 따로 정적 메소드를 선언해서 알고리즘을 구현했다.
보통 인스턴스 메소드를 선언하면 객체를 따로 선언해야 해서 한 문제만 풀 때는 번거롭기도 하고 굳이 그럴 필요가 없어서 다들 정적 메소드를 사용하는 것 같다.
public static void get_prime() {
prime[0] = true; // 소수 아니라서 제외
prime[1] = true; // 소수 아니라서 제외
for(int i=2; i<=Math.sqrt(prime.length); i++) {
for(int j = (i*i); j<prime.length; j += i) {
prime[j] = true;
}
}
}get_prime 메소드는 매개변수도 없고 출력값(리턴하는 값)도 없는 메소드인데, prime이라는 배열은 어디서 가져왔나?
get_prime() 메소드 위에다가 먼저 prime이라는 정적 boolean 타입의 필드를 선언해 주었다. 이렇게!
public static boolean[] prime; // main 메소드 밖에서 선언나는 정적 필드를 선언할 생각은 못 했는데, 생각해 보니 정적 필드를 선언하고 그 필드를 정적 메소드에 언급하면 굳이 로컬변수나 객체를 생성하지 않아도 되겠다.
이렇게 위에서 정적 필드를 선언하고, 나중에 main함수 안에서 prime 배열의 길이만 선언해 주면 된다.
N+1의 길이로 설정해서 0부터 N까지의 소수값 여부를 저장할 수 있는 배열을 만들어 준다.
(정적 필드 prime배열을 N+1의 길이로 설정한 것도, 그냥 0부터 N까지의 수들 중 소수를 다 구해버리고 나중에 M에서 N 사이에 있는 소수 값만 추출하기 위해서인 것 같다. prime배열을 M부터 N까지 선언한다면 기존 에라토스테네스의 체 알고리즘을 일부 변형해야 되서 번거로운 점도 있을 듯.)
prime = new boolean[(N+1)]; // main 메소드 안에서 설정
에라토스테네스의 체 알고리즘은 2개의 중첩 for문으로 구성된다.
1. 여기선 true이면 소수가 아니고 false면 소수라고 간주한다.
2. 이는 어떤 수의 배수는 모두 소수에서 제외한다는 원리를 이용한다.
첫 번째 for문에서의 i는 어떤 수의 역할을 한다.
두 번째 for문에서의 j는 어떤 수의 배수 역할을 한다.
좀 더 구체적으로 보면,
1. 0과 1은 소수가 아니고 2는 소수라서, i=2부터 시작한다.
2. j는 i*i이다. i*i는 i라는 약수를 갖기 때문에 소수에서 제외된다.
3. 이 j에다가 i씩 더한다. 즉 i*i, i*(i+1), i*(i+2), ... 이렇게 해서 i를 약수로 갖는 모든 값들을 제외시킨다.
4. 그 다음은 i=3, 위의 과정을 반복한다. 그런데 만약 i=4처럼 소수가 아닌 값이 i 자리에 와도 이미 i=2일 때 j의 값에 해당되어서 제외되었기 때문에 상관 없다.
5. 이렇게 N까지 반복하는 것이 아니라, N에 루트 씌운 값까지만 반복한다. 그 이후의 값은 검사할 필요가 없다.
+) 5번의 이유:
어떤 자연수 N은 1과 자신이 아닌 다른 두 수 A와 B의 곱으로 나타낼 수 있다고 해 보자. (즉 N은 소수가 아니다.)
A * B = N이다.
그런데 만약 A가 N의 제곱근보다 크다면, 나머지 B는 반드시 N의 제곱근보다 작아야 한다. 안 그러면 A*B는 N보다 큰 값을 갖게 되어서 식이 성립하지 않는다.
=> 즉 N이 소수가 아니라고 가정할 때, N의 제곱근까지만 검사하면 합성수 N을 이루는 두 수 A, B중 작은 수(여기서는 B)까지는 검사할 수 있고, 만약 여기까지 검사했을 때 N의 약수가 나오지 않는다면?
=> B가 없는 것이므로 A*B = N 이라는 가정이 깨지게 된다. 고로 이때 N은 소수가 아니라고 볼 수 있다.
=> N의 제곱근까지만 검사하면 N이 소수인지 아닌지를 알 수 있다!
아무튼 그래서 get_prime() 정적 메소드를 선언해서 N까지의 수 중에서 소수인 값만 찾아 준다.
그 다음에는 main함수에서 해결하면 되는데,
1. if문에서 최솟값인 M이 최댓값인 N보다 큰 예외 상황 및 M, N이 0과 10000 사이가 아닌 예외 경우를 따로 처리한다.
2. 초기 sum 값은 0, min값은 int 타입이 가질 수 있는 가장 큰 값으로 설정하고, 바꿔 나간다.
** 왜 min 값을 0이 아니라 최댓값으로 설정하는지는 잘 모르겠다...!
int sum = 0;
int min = Integer.MAX_VALUE;
// Integer 클래스 안에 MAX_VALUE라는 final static 필드가 선언되어 있어서 이렇게 불러올 수 있나보다.그리고 정적 필드 prime의 각 원소를 for문을 사용해서 하나씩 해당 값이 false인지(=소수인지) 비교하는데, 만약 false라면 sum 값에다 더해 주고, min 값으로 할당해 준다.
for(int i=M; i<=N; i++) {
if(prime[i]==false) {
sum += i;
if(min==Integer.MAX_VALUE) {
min = i;
}
}
}이때, prime의 해당 원소의 값이 false일 때 min의 값을 i로 할당해 줘야 한다.
이렇게 조건을 주면, min값이 초기에 설정한 Integer.MAX_VALUE일 때만 min 값을 i로 할당하는데,
그러면 min값은 한 번만 할당되고 여러 번 변경되지 않는다.
마지막으로, 만약 M부터 N까지의 범위에 소수가 없었을 때, 즉 sum == 0일 때의 조건만 지정해 준다.
if(sum==0) {
System.out.println(-1);
}else {
System.out.println(sum);
System.out.println(min);
}이러면 문제가 풀린다....
<오답분석>
처음에 나는:
1. 에라토스테네스의 체 알고리즘을 쓰지 않고 (=> 효율성 문제)
2. min 값을 0으로 두고 (=> min값을 MAX_VALUE로 두지 않을 경우 오류가 발생되는 데이터가 있었을 것)
3. M, N이 지정한 데이터 값을 벗어났을 경우를 처리하지 않아서 에러가 발생하지 않았을까 생각해 본다.
<의문>
Q1. 왜 min 값을 0으로 설정하면 안 되는지는.... 정말 궁금하다.
Q2. BufferedReader를 쓸 때 InputStreamReader를 같이 쓰는데, 그럼 InputStream과의 차이는 무엇일지 궁금하다.
Step 9-3번 문제(11653번).
주어진 자연수 N을 소인수분해하는 문제.
이번 문제는 혼자 풀었다!
'소수'가 키워드이나, 앞의 소수 판별 문제와는 다른 것이, 가령 거듭제곱으로 A의 k승인 경우 A를 1번만 출력하지 말고 k번 다 출력해야 했다. 그래서 조건이 맞으면 i가 증가하는 for문이 아니라 while문을 사용했다.
1. Import
import java.util.Scanner;
import java.util.ArrayList;1. 입력을 받아야 하므로 Scanner(BufferedReader를 쓰지 않아도 시간 초과가 안 되었다.)
2. N의 약수에 해당하는 수를 저장할 ArrayList. 소인수가 몇 개일지 몰라서 배열 말고 ArrayList를 사용했다.
2. 정적 필드
9-2를 풀면서 정적 필드, 메소드를 잘 활용하면 객체 생성이나 로컬변수 처리 문제를 안 겪어도 된다는 생각에 정적 필드와 메소드를 선언했다.
public static int N;
public static ArrayList<Integer> number = new ArrayList<Integer>();
public static int i = 2;1. N : scanner로 입력받을 N을 다른 메소드에서 다시 정의하기 귀찮아서 정적 필드로 선언.
2. ArrayList도 위에서 import만 해 주면 static field로 선언할 수 있었다...!
3. i는 while문에서 하나씩 증가시키고 해당 조건에 맞으면 소인수로 ArrayList에 추가시킬 수인데, 로컬 변수로 선언했다가 괜히 처리하기 까다로워질 것 같아서 정적 필드로 선언했다.
3. 정적 메소드 선언
자연수 N이 주어지면 해당 자연수를 소인수분해하는 isDivisor() 메소드를 선언하였다.
public static void isDivisor(int N) {
if(N==1) { // 예외1 : N=1일 때
System.out.println("");
}else if(N<0 | N>10000000) { // 예외2 : N이 범위를 벗어날 때
System.out.println("Error");
}else {
while(true) {
if(N==i) { // case 1
number.add(i);
break;
}else if(N % i != 0) { // case 2
i++;
}else if(N % i == 0) { // case 3
N = N/i;
number.add(i);
}
}
for(int k=0; k<number.size(); k++) {
System.out.println(number.get(k));
}
}
}case 1:
소인수분해가 다 완료되고 더 이상 인수(혹은 약수)가 없으면 나눠지고 남은 수인 N과 나눌 수인 i가 서로 같아진다. 이 경우에만 while문을 break하도록 했다.
case 2:
N이 i로 나눠지지 않을 때 = i가 N의 소인수가 아닐 때.
i+1을 해서 값만 변화시켰다.
case 3:
N이 i로 나눠질 때 = i가 N의 소인수일 때.
우선 N을 i로 나눠서 N 값을 변화시키고, 해당 i값을 ArrayList에 추가했다.
i값을 증가시키지 않았으므로, 만약 N이 i로 여러 번 나눠지는 수였다면 그만큼 i가 추가로 ArrayList에 추가되도록 했다.
그리고 이렇게 만들어진 number이라는 ArrayList를 0번부터 끝까지(ArrayList의 size -1까지) 출력시켰다.
4. main 메소드
앞에서 메소드와 필드로 모든 과정을 선언해서 main메소드는 짧게 작성할 수 있었다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
isDivisor(N); // 3번에서 작성한 isDivisor 정적 메소드 사용
sc.close(); // scanner 꼭 닫아주기!
}
Step 9-4. 소수 구하기(1929번)
이 문제도 혼자 풀었다.
<접근>
Step 9-2의 에라토스테네스의 체의 원리를 그대로 활용했다.
다만 아까는 int타입의 sum 변수를 사용한 대신, 지금은 에라토스테네스의 체로 0부터 N까지의 소수를 구한 뒤, M부터 N까지의 소수만 출력하는 방식을 사용하였다.
import java.util.Scanner;
public class Main {
// 정적 필드 선언
public static int M;
public static int N;
public static boolean[] prime;
public static void main(String[] args) {
// 정적 메소드에 사용할 값 할당하기
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
prime = new boolean[(N+1)];
if(M>=1 && N>=M && N<=1000000) {
get_prime(); // 정적 메소드 사용
// 정적 메소드에서는 1~N의 소수를 구했으나, M~N의 소수만 출력
for(int i=M; i<prime.length; i++) {
if(prime[i]==false) {
System.out.println(i);
}
}
}else { // 예외처리 : M과 N의 범위가 잘못되었을 때
System.out.println("ERROR");
}
sc.close();
}
// 정적 메소드 선언
public static void get_prime() {
prime[0] = true;
prime[1] = true;
for(int i=2 ; i<=Math.sqrt(N) ; i++) {
for(int j=(i*i); j<prime.length; j += i) {
prime[j] = true;
}
}
}
}
Step 9-5(4948번)
이것도 혼자 풀었다! 사실 에라토스테네스의 체 원리만 알면 쉽게 풀 수 있는 문제인 것 같다.
<원리>
9-2, 9-4와 마찬가지로 에라토스테네스의 체 알고리즘은 정적 메소드로 선언해 놓은 상태에서 시작하면 편하다.
다만 여기는 여러 개의 test case가 주어지고, 각각 한 줄씩 주어지며, 몇 개가 주어질지 모른다는 점에서 주의해야 한다.
1. N의 입력 여러 개 받기
이때 N은 몇 개가 나올지 모르고 한 줄씩 나오므로, StringTokenizer 등을 사용하지 않아도 분리가 되었다. 나는 원래 분리된 걸 분리하려고 하느라 애를 먹었는데, 원래 스캐너는 입력을 하면 한 줄 단위로 처리하는 거였다.
다만 여러 줄을 입력하고 언제 끝날지 모른다는 점에서 for문보다는 while문이 사용하기 적합했다.
-> 그래서 main메소드 영역을 이렇게 작성했다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
N = Integer.parseInt(sc.nextLine().trim());
if(N==0) {
break;
}
if(N<1 | N>123456) {
System.out.println("ERROR");
break;
}else {
prime = new boolean[((2*N)+1)];
get_prime();
}
}
sc.close();
}입력의 마지막에 0이 주어진다는 말은, 0이 입력으로 주어지면 프로그램을 종료시키라는 말과 같다.
그래서 while문을 두고 break하는 조건을 N==0일 때로 지정했다.
+ 또한 N은 sc.nextLine()으로 입력을 한 줄씩 받아서 처리하도록 했다.
+ N 뒤에는 trim() 메소드를 써서, 혹시나 공백과 섞인 문자열이 들어갔을 때 숫자만 추출할 수 있도록 했다.
2. 에라토스테네스의 체 원리를 이용 + 문제에 맞게 get_prime 정적메소드 다시 정의
우선 정적 메소드에서 사용할 정적 필드를 먼저 정의했다.
public static int N; // main 메소드에서 입력 받을 때 사용
public static boolean[] prime; // 많은 숫자들 각각이 소수인지 아닌지를 저장하기 위한 배열
public static int count = 0; // 특정 범위에서 소수의 숫자를 세기 위한 int 타입 필드public static void get_prime() {
count = 0; // N이 새로 바뀌어서 메소드가 새로 호출될 때마다 count를 0으로 초기화한다.
prime[0] = true;
prime[1] = true;
if(N==1) { // N=1이면 i=2로 시작해서 소수를 셀 수 없으므로 예외로 처리했다.
System.out.println(1);
}else if(N==0) {
System.out.println("");
}else { // 에라토스테네스의 체 알고리즘 그대로 사용
for(int i=2 ; i<=Math.sqrt((2*N)) ; i++) {
for(int j=(i*i); j<prime.length; j += i) {
prime[j] = true;
}
}
//N보다 크고 2N보다 작은 소수들만 출력
for(int i=(N+1) ; i<=(2*N) ; i++) {
if(prime[i]==false) {
count ++; // 소수 하나 나올 때마다 count + 1
}
}
System.out.println(count);
}
}최종 코드는 이렇다.
package ml.app2;
import java.util.Scanner;
public class Main {
public static int N;
public static boolean[] prime;
public static int count = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
N = Integer.parseInt(sc.nextLine().trim());
if(N==0) {
break;
}
if(N<1 | N>123456) {
System.out.println("ERROR");
break;
}else {
prime = new boolean[((2*N)+1)];
get_prime();
}
}
sc.close();
}
public static void get_prime() {
count = 0;
prime[0] = true;
prime[1] = true;
if(N==1) {
System.out.println(1);
}else if(N==0) {
System.out.println("");
}else {
for(int i=2 ; i<=Math.sqrt((2*N)) ; i++) {
for(int j=(i*i); j<prime.length; j += i) {
prime[j] = true;
}
}
for(int i=(N+1) ; i<=(2*N) ; i++) {
if(prime[i]==false) {
count ++;
}
}
System.out.println(count);
}
}
}
Step 9-6(9020번)
다른 블로그의 글을 참고해서 풀었다!
참고한 글: [백준] 9020번 : 골드바흐의 추측 - JAVA [자바] (tistory.com)
[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]
https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때
st-lab.tistory.com
에라토스테네스의 체 알고리즘을 알고 있었으나, 여기서는 주어진 짝수를 소수의 합으로 나타내되, '두 소수의 차가 가장 적은 쌍으로 나타내라'는 조건이 추가적으로 붙어서 그 점이 어려웠던 것 같다. 그래도 내가 생각한 범위에서의 예제 데이터는 처리할 수 있었는데, 왜 오류가 난 것인지는 잘 모르겠다ㅠㅠ
* IndexOutOfBoundsException 예외가 특히 많이 나왔는데, 어디서 나왔는지를 모르겠다...!
일단 풀이 시작>>
<보완할 점>
블로그 글을 보면서 이해하니, 내 코드가 생각보다 많이 복잡했음을 알 수 있었다.
나는 주어진 짝수가 여러 소수의 합으로 나타낼 수 있고, 그게 총 몇 쌍일지를 모르므로 ArrayList 구조를 사용해야 한다고 생각했지만, while문 하나로도 간단하게 코드를 짤 수 있는 문제였다.
<기존 나의 풀이의 개선점>
: 사용하지 않아도 될 변수 + 자료구조가 꽤 많고, 코드가 복잡했다!
import java.io.*;
import java.util.ArrayList; // 사용할 필요가 없었다
public class Main {
public static boolean[] prime = new boolean[10001];
public static int n;
public static ArrayList<Integer> goldberg; // 사용할 필요가 없었다
public static int sub_index; // 사용할 필요가 없었다
public static void main(String[] args) throws IOException {
try { // 사용할 필요가 없었다
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine().trim());
get_prime();
for (int i = 0; i < T; i++) {
n = Integer.parseInt(br.readLine().trim());
goldberg = new ArrayList<Integer>(); // 사용할 필요가 없었다
if (n > 10000 | n < 4) {
bw.write("ERROR");
break;
} else {
get_goldberg();
}
}
bw.close();
}catch(IndexOutOfBoundsException e) {
System.out.println(e);
}
}
public static void get_prime() {
prime[0] = true;
prime[1] = true;
for (int i = 2; i <= Math.sqrt(10000); i++) {
for (int j = (i * i); j < prime.length; j += i) {
prime[j] = true;
}
}
}
public static void get_goldberg() throws IOException { // 사용할 필요가 없었음. 이 긴 걸!
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i=3; i<=(n/2); i+=2) {
if( prime[i]==false && prime[(n-i)]==false) {
goldberg.add(i);
goldberg.add((n-i));
}else if(prime[i]==false && (2*i)==n) {
goldberg.add(i);
goldberg.add(i);
}
}
int min = Integer.MAX_VALUE;
int sub_index = 0;
for (int i = 0; i < goldberg.size(); i += 2) {
int sub = Math.abs(goldberg.get(i) - goldberg.get(i + 1));
if (sub < min) {
sub_index = i;
}
}
bw.write(String.valueOf(goldberg.get(sub_index)) + " ");
bw.write(String.valueOf(goldberg.get(sub_index + 1)) + "\n");
bw.flush();
}
}
<핵심>
1. 한 수의 합이 되는 두 수의 쌍 중 가장 차가 적은 것을 선택하려면, (블로그 글 보면서 배운점)
: 짝수 2N의 경우 N+N에서부터 시작하여, (N-1)+(N+1) 이런 식으로 첫 번째 수는 하나씩 감소, 두 번째 수는 하나씩 증가시킨다. 그러면 두 수의 차가 커지면서 두 수의 합은 그대로 유지된다. 이런 식으로 while문을 전개시키고, 두 수가 모두 소수가 되는 시점에 while문을 break하면 다른 변수를 생성하지 않아도 된다.
2. 주어진 짝수의 범위는 어차피 제한되어 있으니, 처음에 크기가 10001(10000+1)인 boolean 타입의 배열을 만들고 그 범위의 소수를 다 구하는 것이 매번 새로 배열을 만들고 소수를 새로 구하는 것 보다 빠르다. (당연하지만...!)
<코드 다시 작성>
import java.io.*;
public class Main {
public static boolean[] prime = new boolean[10001];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine().trim());
get_prime();
while(T>0) {
int n = Integer.parseInt(br.readLine().trim());
int firstNum = n/2;
int secondNum = n/2;
while(true) {
if(prime[firstNum]==false && prime[secondNum]==false) {
System.out.println(firstNum + " " + secondNum);
break;
}
firstNum--;
secondNum++;
}
T--;
}
bw.close();
}
public static void get_prime() {
prime[0] = true;
prime[1] = true;
for (int i = 2; i <= Math.sqrt(10000); i++) {
for (int j = (i * i); j < prime.length; j += i) {
prime[j] = true;
}
}
}
}
'server-side > JAVA Algorithm' 카테고리의 다른 글
| Chapter 4-1 if문 (0) | 2021.05.04 |
|---|---|
| Chapter 3 (0) | 2021.05.03 |