728x90
SMALL
백준 문제 풀이: 10816 [숫자 카드 2]
문제 링크: https://www.acmicpc.net/problem/10816
문제 설명:
숫자 카드가 여러 개 주어졌을 때, 각 숫자 카드가 몇 개 있는지 구하는 문제입니다. 입력으로 주어지는 숫자 범위는 -10,000,000부터 10,000,000까지입니다. 이를 효과적으로 처리하기 위해 정수 범위를 배열로 매핑하여 카운트를 저장합니다.
문제 해결 코드
#include <iostream>
using namespace std;
int d[20000001];
int arr[500001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
if (arr[i] < 0) {
d[((-1) * arr[i]) + 10000000]++;
} else {
d[arr[i]]++;
}
}
cin >> m;
int x;
for (int i = 0; i < m; i++) {
cin >> x;
if (x < 0) {
cout << d[((-1) * x) + 10000000] << ' ';
} else {
cout << d[x] << ' ';
}
}
}
코드 설명
- 핵심 알고리즘: 배열을 이용한 빈도 카운팅
- 구현 세부사항:
- 주어진 숫자 범위는 -10,000,000부터 10,000,000까지입니다. 이를 배열
d
에 매핑하기 위해 음수는 배열의 인덱스 10,000,001부터 저장합니다. - 숫자를 입력받아 배열의 해당 인덱스 값을 증가시켜 카운트를 기록합니다.
- 질의할 숫자의 빈도는
d
배열에서 해당 숫자의 인덱스를 참조하여 바로 출력합니다.
- 주어진 숫자 범위는 -10,000,000부터 10,000,000까지입니다. 이를 배열
- 시간 복잡도: O(n + m)
- 숫자 카드 입력: O(n)
- 질의 처리: O(m)
결과
주어진 숫자 카드와 질의 숫자에 대해 효율적으로 빈도를 계산하고 출력했습니다. 배열을 이용한 간단한 접근법으로 문제를 해결하였습니다.
다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!
728x90
LIST
'BAEKJOON > 자료 구조' 카테고리의 다른 글
백준 10845번 [큐](C++)-yes6686- 티스토리 (0) | 2024.01.05 |
---|---|
백준 10828번 [스택](C++)-yes6686- 티스토리 (1) | 2024.01.05 |
백준 10773번 [제로](C++)-yes6686- 티스토리 (0) | 2024.01.03 |
백준 9012번 [괄호](C++)-yes6686- 티스토리 (0) | 2024.01.03 |
백준 4949번 [균형잡힌 세상](C++)-yes6686- 티스토리 (0) | 2024.01.03 |