숫자 카운팅 알고리즘 C++ / Java / 파이썬 시간복잡도

백준 10807번 : 개수 세기 문제를 풀면서 숫자 카운팅하는 알고리즘에 대해 알아봅시다.

 

주어진 숫자에서 특정 숫자의 개수를 세는 문제입니다.

O(N) 시간복잡도로 for문 한 번이면 풀 수 있는 간단한 문제입니다.

 

https://www.acmicpc.net/problem/10807

10807번: 개수 세기

 

 

정수의 개수 N은 100개, 입력 범위는 -100~100으로 시간초과나 데이터형 선택에도 특별히 고려할 내용은 없네요.

빠르게 풀어봅시다.

 

1. C++

conut 변수에 숫자를 세고 출력하면 되겠네요.

#include <iostream>
using namespace std;

int main() {
	int N, v, count=0;
	int arr[100] = {};
	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> arr[i];
	}
	cin >> v;
	for (int i = 0; i < N; i++){
		if (arr[i] == v){
			count++;
		}
	}
	cout << count;
	return 0;
}

 

2. JAVA

C++과는 다르게 배열에 저장하지 않고 StringTokenizer에서 바로 꺼내서 비교해보았습니다.

사실 속도나 성능에 크게 차이는 없지만 불필요한 배열선언과 코드량을 줄이기 위함입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(br.readLine());
		int count = 0;
		
		for(int i = 0; i < N; i++){
			if(v == Integer.parseInt(st.nextToken())){
				count++;
			}
		}
		System.out.println(count);
	}
}

 

3. Python 파이썬

파이썬 풀이는 3줄로 끝납니다.

파이썬의 탄생 이유는 우리의 소중한 개발 시간을 줄이는 것에 있습니다.

1라인 : 숫자가 몇개인지 N 입력값은 중요하지 않습니다.

2라인 : 숫자 배열을 a로 저장합니다.

3라인 : 몇개가 있는지 리턴하는 count 함수를 사용합니다.

N=input()
a=input().split()
print(a.count(input()))

 

최소 / 최대값을 찾거나, 특정 숫자를 찾는 일은 반복문 1회 수행이 필요합니다.

빅오표기법 시간복잡도로 위 소스의 수행시간을 표현하면 O(N)이라고 합니다.

N이 1억이 넘어가면 수행시간은 대략 1초로 계산합니다.