[C/C++]백준 10807번 - 개수 세기

 

문제 링크 : https://www.acmicpc.net/problem/10807

10807번: 개수 세기

---

접근방식

2가지 풀이를 생각해 볼 수 있다.

1번째) 그냥 단순하게 배열을 처음부터 순회하면서 정수v의 개수를 확인하는 방법.
2번째) 배열의 저장공간을 좀 더 써서 입력받은 정수들을 배열의 대응되는 인덱스의 값을 1씩 증가시키는 방식.

2번째 방법에는 좀 변형이 필요하다. v의 구간때문이다. (-100<= v <= 100). v의 값이 마이너스도 가지는데, 배열의 인덱스는 마이너스가 될 수 없기 때문에 v + 100 을 인덱스의 값으로 사용할 것이다.

다시 말해서, 배열의 인덱스 0부터 100까지를 -100부터 0의 정수를 저장하는데 사용하고, 배열의 인덱스 101 부터 200까지를 1부터 100 까지의 정수를 저장하는데 사용할 것이다. v와 관련된 식으로  써보면,

코드: arr[v + 100] += 1;

위와 같다.  2번째 방식으로 하면, O(1) 시간에 답을 찾을 수 있다.

근데 문제를 다 풀고 다시 생각해보니까,  입력 받을 정수의 개수 N의 최대값이 100으로 굉장히 작아서 속도 면에서는 둘다 비슷하다.
오히려 2번째는 첫 번째 방식보다 메모리를 2배나 더 사용해야하기 때문에, 1번째 방식이 더 좋은 방식이라 생각한다.
1번째 방식이 반복문을 2번 돌아도 n의 범위가 작아서 성능상으로는 크게 차이는 없을 듯?

1번째 풀이 코드

//1번째 방식
#include<cstdio>

int arr[100];

int main()
{
	int n;
	int target;
	int input;
	int count = 0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", arr + i);
	}

	scanf("%d", &target);
	
	for (int i = 0; i < n; i++) {
		if (arr[i] == target) count += 1;
	}
	
	printf("%d\n", count);
	
	return 0;
}

 

2번째 풀이 코드

//2번째 방식
#include<cstdio>

int arr[201];

int main()
{
	int n;
	int target;
	int input;
	int count = 0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		arr[100 + input] += 1;
	}

	scanf("%d", &target);

	count = arr[target + 100];
	printf("%d\n", count);

	return 0;
}

 

다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-

DaeeYong/Algorithm-Solution-