풀었던 문제들을 어떤 과정을 통해 풀게 되었는지 단순히 기록하는 포스팅 입니다.
결과는 정답이지만 풀이 과정이 효율적이지 않거나 올바르지 않을 수 있다는 점 참고 부탁드립니다.
또한, 풀이 과정이 특정 언어(Java)에 치우쳐 진행될 수 있습니다.
문제 개요
문제 출처 : https://www.acmicpc.net/problem/27650
2023 성균관대학교 프로그래밍 Open Contest에 출제된 문제 입니다.
풀이
이 문제는 인터렉티브 문제입니다.
입출력을 테스트하기 까다롭기 때문에 먼저 문제를 풀 방법을 확실하게 생각하고 코드를 작성하였습니다.
저는 가장 먼저 이 지문에 대해 생각을 하였습니다.
질문은 최대 20번 할 수 있고.. 질문에 대한 답변을 기반으로 하여
5,000,000개의 수 중에서 마법박스에 들어있지 않은 수들 중 최솟값을 구하는 문제입니다.
어떻게 20번의 질문 만으로 마법박스에 들어있지 않은 수를 구할 지가 중요하다는 생각이 들었습니다.
N은 항상 최대값 5,000,000이라는 가정을 해보도록 하겠습니다.
N부터 2까지 순차적으로 질문하면서 1이 나올 때 까지 질문하거나
2부터 시작해서 N까지 질문하여 0이 나올 때 까지 질문하는 방법이 있겠습니다.
하지만 최악의 경우 (2가 없거나, 5,000,000이 없거나)
20번의 질문으로는 어림도 없습니다. 이 방법은 사용하지 못하겠네요.
그렇다면 정렬된 수들 중에서 원하는 값을 찾는 방법 중 가장 빠른 방법인 이분탐색을 사용한다면 어떨까요?
만약 500이라는 수가 마법박스에 들어 있는지 물어본다고 가정하겠습니다.
만약, 결과가 1이 나온다면 500 이하의 수는 모두 마법박스에 들어 있다는 의미이므로 500보다 큰 수들로만 해서 다시 질문할 수 있습니다.
만약, 결과가 0이 나온다면 500이라는 수는 정답 후보 중 하나가 될 수 있겠네요.
혹시나 더 작은 수가 박스에 들어있지 않은지만 질문하여 확인하면 됩니다.
이분탐색은 겨우 log N번만큼의 과정으로 원하는 값을 찾을 수 있습니다.
5,000,000에 밑이 2인 log를 취하면 22.2534... 가 나오므로 총 23번의 질문이 필요함을 알 수 있습니다.
(전 수학에 대한 감이 부족해서 당시 그냥 계산기로 5,000,000을 1 이하의 수가 나올 때까지 2로 나눴습니다;;)
아쉽게도 이분 탐색만으로는 20번의 질문 안에 정답을 찾을 수 없겠네요!
저는 여기서 이분탐색을 수행하는 숫자들의 갯수를 줄이자는 생각을 하였습니다.
2^20 = 1,048,576 이므로
n을 약 1,000,000까지만 줄이면 20회 안에 원하는 값을 찾을 수 있는것을 알 수 있습니다.
다음으로 이 지문에 대해 생각을 해보겠습니다.
만약 마법박스에 숫자 2가 들어있다고 가정해보면 마법박스에는 위 그림과 같이
2부터 시작하는 짝수 (2의 배수)가 모두 저장되어 있을 것입니다.
그렇다면 저장되어 있지 않은 수는 어떤 수들 일까요?
바로 홀수 입니다. (2의 배수가 아닌 수)
그렇다면 만약 2, 3, 4, 5, 6, 7, 8, 9 까지 저장되어 있다고 가정해 봅시다.
저장되어 있지 않은 수는 어떤 수들 일까요?
2의 배수가 아니고, 3의 배수가 아니고, 4... 5... 6... 7... 8... 9...
어렵지만 이 모든 조건을 충족할 만한 수는...?
바로 소수(Prime Number)입니다.
소수는 1과 자기 자신을 제외한 수로 나눠지지 않는 수죠?
(2, 3, 5, 7, 11, 13, 17, 19 등등...)
즉, 1과 자기 자신을 제외한 수의 배수가 될 수 없다는 의미 입니다.
(또한 2를 제외하면 모든 소수는 홀수겠죠?)
그렇다면 만약 2부터 N까지의 수 중 에서 소수 만으로 질문을 한다면
마찬가지로 정답을 알아낼 수 있지 않을까 생각하였습니다.
그렇다면 2부터 N까지의 소수 개수는 몇 개일까요?
import java.util.LinkedHashSet;
public class Main {
public static void main(String[] args) {
final int N = 5_000_000;
HashSet<Integer> primeSet = new HashSet<>(N-1);
for(int i = 2; i <= N; i++) primeSet.add(i);
for(int i = 2; i*i <= N; i++) {
if(primeSet.contains(i)) {
for(int j = i*i; j <= N; j+= i) primeSet.remove(j);
}
}
System.out.println("2~N 까지 소수의 개수 : ");
System.out.println(primeSet.size() + " 개");
}
}
에라토스테네스의 체 방법을 사용하여 소수의 개수를 구한 결과
348,513개가 있다는 것을 알 수 있었습니다.
목표로 하던 1,000,000보다 한참 적은 수네요!
그렇다면 이 문제를 어떻게 풀어야 할 지에 대한 스케치는 다 그려진 상태입니다.
"2부터 N까지의 소수들로 이분탐색(질문)을 수행하여 박스에 들어있지 않은 값 중 최솟값을 알아내자"
여기서부터는 Java에 치우쳐 풀이가 이루어집니다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
LinkedHashSet<Integer> primeSet = new LinkedHashSet<>(N-1);
for(int i = 2; i <= N; i++) primeSet.add(i);
for(int i = 2; i*i <= N; i++) {
if(primeSet.contains(i)) {
for(int j = i*i; j <= N; j+= i) primeSet.remove(j);
}
}먼저 처음 소수의 개수를 구하는 코드와 동일하게 HashSet 으로 소수를 추출해내기로 하였습니다.
HashSet이 개인적으로 에라토스테네스의 체를 구현하는데 가장 직관적이라고 생각하였기 때문입니다.
그 중 LinkedHashSet으로 한 이유는 오름차순으로 정렬되길 원했기 때문입니다.
LinkedHashSet은 foreach 등등의 작업을 수행할 때
add된 순서대로 추출되는 것이 보장되는 것으로 알고 있습니다.
ArrayList<Integer> primeList = new ArrayList<>(primeSet.size());
primeList.addAll(primeSet);LinkedHashSet과 에라토스테네스의 체를 사용하여 2부터 N까지의 소수를 구하는 것은 성공했지만
이분탐색을 위해서는 소수를 배열과 같은 Index 방식으로 저장하는 것이 필요하였습니다.
배열을 사용하여도 좋지만 저는 ArrayList를 사용하기로 하였습니다.
ArrayList의 addAll 함수를 통해 LinkedHashSet에 있는 소수들을 그대로 복사해서 가져옵니다.
LinkedHashSet이기 때문에 굳이 ArrayList를 N log N으로 정렬할 필요 없이 오름차순으로 가져옵니다.
int T = N; // 정답을 저장. (우선 아무 값으로 초기화)
int Q = 20; // 남은 질문 기회
// 이분 탐색
int start = 0;
int end = primeList.size() - 1;
while(--Q >= 0) {
int mid = (start + end) / 2;
int i = primeList.get(mid); // 가운데에 위치한 소수
// 질문 (i 이하의 2 이상의 양의 정수가 마법박스에 모두 들어있는가?)
System.out.println("? " + i);
System.out.flush();
// 답변을 받음
byte result = sc.nextByte();
// 다음 이분 탐색을 진행할 수 없는 경우 break 처리
if(start == end) {
if(result == 0) T = i;
break;
}
// 특정 값을 찾는 문제가 아니기 때문에
// 일반적인 이분 탐색과는 다르게 가능한 계속 질문하면서
// 결과가 0이 나오는 i를 저장 해둔다.
else {
if(result == 1) {
start = mid + 1;
} else {
end = mid - 1;
T = i;
}
}
}
// 정답을 출력
System.out.println("! " + T);
System.out.flush();이후는 이분탐색을 수행합니다.
인터렉티브 방식에 맞게 질문을 하면서 받은 답변을 기준으로
start와 end를 조정하고
최종적으로 T를 출력하면 됩니다.
start와 end가 같은 경우 예외처리만 하면 되겠네요.
소스 코드
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// 2부터 N까지의 수를 LinkedHashSet에 저장합니다.
// N-1개의 숫자를 우선 저장하는 것이 분명하기 때문에 initialCapacity를 N-1로 지정하였습니다.
LinkedHashSet<Integer> primeSet = new LinkedHashSet<>(N-1);
for(int i = 2; i <= N; i++) primeSet.add(i);
// "에라토스테네스의 체" 방식을 통해 소수가 아닌 수는 제외하였습니다.
for(int i = 2; i*i <= N; i++) {
if(primeSet.contains(i)) {
for(int j = i*i; j <= N; j+= i) primeSet.remove(j);
}
}
// 소수들의 목록을 Index로 참조하기 위해 ArrayList를 사용합니다.
// 처음부터 ArrayList로 소수를 걸러내지 않은 이유는 ArrayList.Remove의 시간복잡도 때문입니다.
// 또한, HashSet이 아닌 LinkedHashSet을 사용 한 이유는 모든 소수가 ArrayList에 오름차순으로
// 정렬되어 저장되길 원했기 때문입니다. (HashSet은 순서를 보장하지 않는 것으로 알고 있습니다)
ArrayList<Integer> primeList = new ArrayList<>(primeSet.size());
primeList.addAll(primeSet);
int T = N; // 정답을 저장
int Q = 20; // 남은 질문 횟수
// 이분탐색을 사용하여 마법박스에 들어있지 않은 수들 중 최솟값을 찾습니다.
int start = 0;
int end = primeList.size() - 1;
while(--Q >= 0) {
int mid = (start + end) / 2;
int i = primeList.get(mid); // List 중앙에 위치한 소수를 가져옵니다.
// i 이하의 2 이상의 양의 정수가 마법박스에 모두 들어있는지 질문합니다.
System.out.println("? " + i);
System.out.flush();
// 답변을 받습니다.
byte result = sc.nextByte();
// 만약 더 이상 이분탐색을 수행할 수 없다면 질문을 종료합니다.
if(start == end) {
if(result == 0) T = i; // 마지막 질문에 대한 답변이 0이었다면 정답은 i
break;
}
// 답변에 따라 start 또는 end를 조정합니다.
else {
if(result == 1) {
// 2 이상, mid 이하의 양의 정수가 마법박스에 모두 들어 있다
// mid 왼쪽으로는 더 이상 볼 일이 없다
start = mid + 1;
} else {
// 그렇지 않다
// mid 왼쪽만 보면 된다
end = mid - 1;
T = i; // 우선 i를 정답으로 저장 해놓는다.
}
}
}
// 정답을 출력합니다.
System.out.println("! " + T);
System.out.flush();
}
}
풀이에 대한 의견을 댓글을 통해 자유롭게 남겨주시면 감사하겠습니다.