본문 바로가기

BAEKJOON/자료 구조

백준 10816번 [숫자 카드 2](C++)-yes6686- 티스토리

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 배열에서 해당 숫자의 인덱스를 참조하여 바로 출력합니다.
  • 시간 복잡도: O(n + m)
    • 숫자 카드 입력: O(n)
    • 질의 처리: O(m)

결과

주어진 숫자 카드와 질의 숫자에 대해 효율적으로 빈도를 계산하고 출력했습니다. 배열을 이용한 간단한 접근법으로 문제를 해결하였습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!

728x90
LIST