제가 직접 경험 해본 결과, 숫자의 개수를 세는 프로그램을 만드는 것은 생각보다 간단한 일입니다. 이 글에서는 n개의 숫자가 주어지고, q개의 질문이 주어질 때 각각의 질문에 대해 특정 숫자가 몇 개 있는지를 세는 방법을 알려드리겠습니다.
입력 형식 이해하기
가장 먼저, 문제를 이해하기 위해서 입력 형식을 살펴보면, 첫 번째 줄에는 숫자의 개수 n과 질문의 개수 q가 주어집니다. 이어서 두 번째 줄에 n개의 숫자가 입력되고, 마지막 줄에는 q개의 질문이 주어집니다. 아래와 같은 형식을 따릅니다:
입력 예시:
10 4
1 3 4 3 2 3 1 2 5 10
1 3 9 10
이 입력 예시에 따르면, 10개의 숫자 중에서 1, 3, 9, 10이 각각 몇 개인지 세어보는 것입니다.
출력 형식
각 질문에 대하여 해당 숫자의 개수를 출력해야 합니다. 예시의 경우, 결과는 다음과 같습니다:
2
3
0
1
여기에서 각 숫자는 변수에 해당하며, 우리가 원하는 출력을 위해 코드를 작성하는 것이지요.
코드 작성하기
제가 알아본 바로는, Java로 작성된 아래의 코드를 사용해 적용할 수 있습니다. 이 코드는 주어진 n개의 숫자를 정렬하고, 각 질문에 대해 이분 탐색을 통해 개수를 세는 형식입니다.
“`java
import java.util.*;
public class Main {
public static ArrayList
public static long result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a;
int b;
long c[];
int d[];
int count = 0;
long max = Integer.MIN_VALUE;
a = sc.nextInt();
b = sc.nextInt();
c = new long[a];
for (int i = 0; i < a; i++) {
c[i] = sc.nextLong();
if (c[i] > max) max = c[i];
}
sort(c, 0, a - 1);
for (int i = 0; i < b; i++) {
long find = sc.nextLong();
System.out.println(countN(0, a - 1, c, find));
}
sc.close();
}
public static int countN(int s, int e, long[] c, long b) {
if (s > e) return 0;
else if (s == e) {
if (c[s] == b) return findSame(c, b, s);
else return 0;
} else {
int mid = (s + e) / 2;
Long result = c[mid];
if (result == b) return findSame(c, b, mid);
else if (result > b) return countN(s, mid - 1, c, b);
else return countN(mid + 1, e, c, b);
}
}
public static int findSame(long[] c, long b, int k) {
int left = k - 1;
int right = k;
int count = 0;
while (k < c.length && c[k] == b) {
k++;
count++;
}
while (left >= 0 && c[left] == b) {
left--;
count++;
}
return count;
}
public static void sort(long[] data, int l, int r) {
int left = l;
int right = r;
long pivot = data[(l + r) / 2];
do {
while (data[left] < pivot) left++;
while (data[right] > pivot) right--;
if (left <= right) {
long temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}
} while (left <= right);
if (l < right) sort(data, l, right);
if (r > left) sort(data, left, r);
}
}
“`
코드 분석
이 코드의 구조는 다음과 같습니다:
- 입력 받기: n개 숫자와 q개 질문을 입력 받습니다.
- 정렬: 입력받은 숫자들을 정렬하여 이분 탐색을 통해 각 숫자의 개수를 빠르게 셉니다.
- 이분 탐색: 각 질문에 대해 이분 탐색을 실행하여 해당 숫자의 개수를 세어서 출력합니다.
코드를 실행하면 n개의 숫자와 q개의 질문에 대해 빠르게 답을 얻을 수 있습니다.
효율성 검토
- 질문의 개수 q가 많고, 숫자의 개수 n 또한 크면 그에 따라 성능이 저하될 수 있습니다.
- 정렬은 O(n log n)이고 각 질문에 대해 이분 탐색을 쓰기 때문에 시간 복잡도는 O(q log n)입니다.
결론
아래를 읽어보시면, 숫자의 개수를 세는 문제는 코드 구현을 통해 효율적으로 해결할 수 있습니다. 주어진 입력을 탐색하여 어떻게 원하는 숫자의 개수를 세는지 궁금했다면, 간단하게 시도해볼 수 있을 거예요!
키워드: 숫자세기, 알고리즘, java, 이분탐색, 질문, 정렬, 배열, 성능, 문제풀이, 효율성, 프로그래밍