백준(BAEKJOON): 나머지(3052번)

문제

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

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

입력

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

출력

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

예제 입력

39
40
41
42
43
44
82
83
84
85

예제 출력

6

힌트

39, 40, 41, 42, 43, 44, 82, 83, 84, 85를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 모두 6개가 있다.

출처: Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #1 1번

해설

결과를 얻어 내는 방식이 여럿이다. 여기에서는 나머지(1~41)의 출현 빈도를 확인하는 방식을 통해 요구하는 결과를 얻을 것이다.

우선 int형 메모리 42개를 배열로 잡고 그 값을 모두 0으로 초기화한다. 각 배열의 인덱스는 입력된 수를 42로 나눈 나머지에 대응한다. 즉 arr[0]은 해당하는 수를 42로 나눈 나머지가 0인 방이라는 의미이며, arr[41]은 그 나머지가 42인 방인 셈이다. 만약 A라는 수가 입력되고 그 수를 42로 나눈 나머지가 5라면 배열 arr[5]에 1을 더한다. 이러한 방식으로 입력된 수를 처리하면 1~41의 나머지가 출현하는 빈도 arr[] 원소의 값이 되는다. 따라서 각 배열 중 그 값이 1 이상 경우만 세면 문제에서 요구하는 서로 다른 값인 나머지의 개수가 된다.

소스코드 c

#include <stdio.h>

int main(int argc, char *argv[])
{
    int input, i, count = 0;
    int arr[42];

    for (i = 0; i < 42; ++i) {
        arr[i] = 0;
    }

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

    for (i = 0; i < 42; ++i) {
        if (arr[i] >= 1) {
            count++;
        }
    }

    printf("%d\n", count);
    return 0;
}

소스코드 Python3

num_list = list()
for _ in range(10):
    num = int(input())
    num_list.append(num % 42)
num_list = set(num_list)
print(len(num_list))

파이썬의 코드에서 핵심은 리스트를 세트로 바꾸는 것이다. 리스트는 원소의 중복을 허용한다. 따라서 a = [1, 2, 3, 2, 5, 2, 0, 1]과 같은 리스트가 가능하다. 한편 세트는 원소의 중복을 허용하지 않는다. 따라서 리스트 a를 세트로 변환하게 되면 중복되는 원소는 하나만 남게 되므로 a = {0, 1, 2, 3, 5}와 같이 변하게 된다. (물론 이처럼 정렬되는 것은 아니고 편의상 원소를 정렬하였을 뿐이다.) 이러한 자료형의 특성이 이용하여 문제에서 원하는 중복되지 않는 나머지의 개수를 센 것이다. 즉 위 코드에서는 세트형으로 변환된 num_list의 원소 개수를 len()으로 받아 출력한다.