[백준/C] 3052번 - 나머지

주어진 10개의 수를 42로 나눈 나머지 중 서로 다른 숫자의 개수를 세는 문제이다.

 

예전에 Java로도 풀어본 적이 있지만, C로 풀려고 정주행 중 문제를 다시 보니 어떻게 풀었는지 기억이 나지 않았다.

예전에 푼 것 참고해서 풀어도 되지만 다시 스스로 해보고 싶어서 고민해서 풀었다.

 

 

서로 다른 수가 몇 개 있는지 구하는 알고리즘을 어떻게 짤 것인가?

 

고민하다가, 먼저 나머지들을 크기 순으로 정렬하고 반복문으로 이전과 다른 수가 나올 때마다 count 변수에 1을 추가하는 식으로 풀면 되겠다고 생각했다.

 

#include <stdio.h>

int main(){
    int nums[10], temp, count=1; // 변수 선언
    
    // 입력 값을 빈 배열에 넣고 42로 나눈 나머지로 초기화
    for(int i=0;i<10;i++){
        scanf("%d", &nums[i]);
        nums[i]%=42;
    }

	// 크기 순으로 정렬
    for(int i=0;i<9;i++){
        for(int j=i+1;j<10;j++){
            if(nums[i]>nums[j]){
                temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }
    
    // 정렬된 배열 내 요소를 차례로 돌며 다음 인덱스 값이 현재 값과 다를 경우 count 증가
    for(int i=0;i<9;i++){
        if(nums[i]!=nums[i+1])
            count++;
    }
    
    printf("%d", count);
    
    return 0;
}

 

예전에 Java로 어떻게 풀었는지 도무지 기억이 나지 않아 다시 찾아봤다. 과정은 다음과 같았다.

1. 42로 어떠한 수를 나눌 경우 나올 수 있는 나머지는 0~41이므로 길이 42의 배열을 만든다.

2. 10개의 수에 대해 각각을 나눈 나머지를 배열의 해당 인덱스에 대응하여 그 인덱스를 증가시킨다.

    ex) 나머지가 41이면 인덱스 41번에 +1 

3. 배열에서 0이 아닌 요소가 몇 개인지 센다.

 

같은 문제도 여러 방법으로 풀 수 있다는 게 정말 재미있다!