백준 3052번 배열 원소 서로 다른 값 찾기

문제

두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지 이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0, 2이다. 

수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 열번째 줄 까지 숫자가 한 줄에 하나씩 주어진다. 이 숫자는 1,000보다 작거나 같고, 음이 아닌 정수이다.

출력

첫째 줄에, 42로 나누었을 때, 서로 다른 나머지가 몇 개 있는지 출력한다.

---

 우선적으로 생각할 수 있는것은 배열을 활용하여 해결할 수 있다.

나머지를 배열의 원소로 저장하는 배열을 만들 생각을 하고 

우선 입력값을 저장할 배열 (배열 A[10])을 만들었다.(코드를 간략화 하기 위해서는 이 배열을 굳이 만들지 않아도 되긴하다.)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int A[10];
	int B[42] = { 0 };
	
	int count = 0;
	for (int i = 0; i < 10; i++) {
		scanf("%d", &A[i]);
	}

	for (int i = 0; i < 10; i++) {
		if (B[A[i] % 42] == 0) {
			B[A[i] % 42] = 1;
			count++;
		}
	}
	printf("%d", count);
	return 0;
}

나머지가 한번이라도 나오면 배열 B의 값을 1로 바꾸도록 설정하고 count를 1 올린다.

그리고나서 count를 출력하면 배열B에서의 1의 값을 갖는 나머지들을 인덱스넘버로 확인할 수 있다. 

아래는 확인차 배열B를 출력하도록 나타내었다.

나머지로 0,1,2,39,40,41을 가진다는 것을 확인할 수 있다.

---

알고리즘을 정리하자면 다음과 같다.

1.입력값을 가지는 배열을 만든다.

2.나머지 값을 가지는 배열을 인덱스 넘버가 각각의 나머지를 의미하도록 배열을 만든다.

3.나머지 값에 따라 인덱스 넘버가 부여되고 그 배열의 원소의 값을 1로 수정한다.

4.1로 수정된 횟수만큼 count를 올려 서로다른 원소의 개수를 센다.

5.count를 출력한다.

---

하지만 위 코드로는 나머지들이 어떤 종류가 나왔는지만 확인할 수 있고, 어떤 나머지 값이 여러번 나온다면 몇 번 나왔는지는 확인할 수 없다. 따라서 다음과 같이 코드를 수정하면 나머지값이 몇번 씩 나왔는지도 확인할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int A[10];
	int B[42] = { 0 };
	
	int count = 0;
	for (int i = 0; i < 10; i++) {
		scanf("%d", &A[i]);
	}

	for (int i = 0; i < 10; i++) {
		//B배열의 값을 0에서 1로 바꾸는것이 아니라 나온 횟수만큼 1을 증가하도록 변경
			B[A[i] % 42] += 1;	
			count++;
		}
for (int i = 0; i < 42; i++) {
	printf("B[%d]=%d\n", i, B[i]);
}
	printf("%d", count);
	return 0;
}

 

그러나 확인해보니 10이 출력되어 뭔가 이상하다는 것을 느낄 수 있다.

원래 정상적인 출력값으로는 6을 출력해야하는데 10이 나오는 것을 확인할 수 있다. 

이는 조건문이 사라지면서 블록의 반복을 할 때 마다 그냥 count를 증가시켜서 그렇다. 

따라서 count를 따로 반복문을 만들어 횟수를 세어주는것이 좋다.

수정된 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int A[10];
	int B[42] = { 0 };
	
	int count = 0;
	for (int i = 0; i < 10; i++) {
		scanf("%d", &A[i]);
	}

	for (int i = 0; i < 10; i++) {
			B[A[i] % 42] += 1;
		}
	for (int i = 0; i < 42; i++) {	//배열의 서로 다른 수를 세어주기 위한 또 다른 반복문
		if (B[i] >= 1) {	//주의할점은 B[A[i]%42]가아니라 B[i]로 확인해야한다.
			count++;
		}
	}
for (int i = 0; i < 42; i++) {	//확인차 배열을 출력하는 코드 정답제출에는 필요없다.
	printf("B[%d]=%d\n", i, B[i]);
}
	printf("%d", count);
	return 0;
}

주석에 적었듯이

배열 B에서 1이상의 값을 갖는 인덱스들을 세는것은

이미 저장된 배열 B의 원소 B[0]~B[41]까지에서 확인하는 것이기 때문에 B[i]로 확인하며 count++하는것이 옳다.

입력값과 비교해 보면 나머지 0이2번,1이2번,39가1번40이2번41이2번 나왔음을 확인할 수 있다.