[BOJ] 백준 10807. 개수 세기

0. 문제 링크

10807번: 개수 세기 (acmicpc.net)

10807번: 개수 세기

 

1. 문제 및 입,출력 정의

---

Q. 총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오.

 

Input. 

첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거나 같으며, 100보다 작거나 같다.

 

Output.

첫째 줄에 입력으로 주어진 N개의 정수 중에 v가 몇 개인지 출력한다.

 

2. 접근

---

 (1) 첫째 줄에 주어진 수만큼 반복하여 입력받은 정수를 배열에 채운다.

 (2) 배열을 반복해서 탐색하여 세번째 줄에 입력받은 정수와 비교하여 count를 늘린다.

 

3. 코드 - python

---

n = input()
arr = input().split()
    
x = input()

result = 0

for a in arr :
    if x == a :
        result += 1
print(result)

python에서는 사실 첫번째 줄 입력값은 의미가 없다.  하지만 배열의 크기를 정해두는 편이 좋은 타 언어에서는 필요.

 

4. 결과 및 성능 개선

---

 

 

맞긴 한데 확실히 많이 느리다. 만족스럽지 않아 CPP로 재도전..!

 

#include <iostream>
int main() {
    int a, b[100], c, cnt;
    cnt = 0;
    std::cin >> a;
    for (int i = 0; i < a; i++) {
        std::cin >> b[i];
    }
    std::cin >> c;
    for (int i = 0; i < a; i++) {
        if (c == b[i]) cnt++;
    }
    std::cout << cnt;
    return 0;
}

 

 

문제를 코드로 그대로 옮겨서 풀면 여기까지만 해도 괜찮다. 하지만 좀더 빠르고 단순하게 푼다면

 

#include <iostream>
int main() {
    int a, c;
    int b[201] = { 0, };
    std::cin >> a;
    while(a--) {
        std::cin >> c;
        b[c + 100]++;
    }
    std::cin >> a;
    std::cout << b[a + 100];
    return 0;
}

 

입력받을 정수가 -100~100이기 때문에 그냥 201짜리 배열을 만들어 들어오는 정수의 index를 count해주면 된다.

 

여기서 메모리까지 절약하려면 C언어로 넘어가서..

#include<cstdio>
int d[201],t,n;
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d",&t);
		d[t+100]++;
	}
	scanf("%d",&t);
	printf("%d",d[t+100]);
}

 

완전히 동일한 코드지만 메모리 사용량을 2020KB에서 1112KB까지 줄일 수 있다. 

(아마도 CPP에서 main문 실행 이전에 메모리 사용하는게 좀 많아서 그런듯..?)

더 줄이려면 언어를 C++17에서 버전을 좀 더 낮춘 cpp로 가거나 할 수 있지만 여기까지만 하는걸로!