[백준/Java] 3052번 - 42로 나눈 나머지 가짓수 세기

10개의 0 이상의 정수가 입력되었을 때, 각각을 42로 나눌 경우 도출되는 나머지의 가짓수를 세어야 하는 문제다.

 

접근 방법은 이렇다.

 

1. 어떠한 수를 42로 나누었을 때 나머지는 0~41

2. 길이가 42인 배열의 인덱스(0~41)에 나머지를 대응하여 해당 인자에 +1

3. 배열의 인자가 0이 아닐 경우 새로운 변수 count에 +1

4. count 출력

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[] array = new int[42]; // 42로 나눈 나머지 넣을 배열
        int num;
        
        for (int i=0;i<42;i++) // 배열 인자 0으로 초기화
            array[i] = 0;
        
        for (int i=0;i<10;i++) {
            num = Integer.parseInt(br.readLine()); // 입력된 숫자 읽기
            array[num%42]++; // 나머지의 크기에 따라 배열의 해당 인덱스에 1씩 추가(체크)
        }
        
        // 나머지가 몇 가지인지 세기
        int count = 0;
        for (int i=0;i<42;i++) {
            if (array[i] != 0)
                count++;
        }
        
        System.out.println(count);
        
    }
}

 

하지만 이 코드의 경우, 같은 크기의 나머지가 여럿 나온다면 이것은 메모리와 시간의 낭비를 불러올 것이다.

우리가 원하는 것은 어떠한 나머지가 존재하느냐 그렇지 않느냐지 몇 개 존재하는지가 아니기 때문이다.

 

그래서 개선해 보았다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[] array = new int[42];
        int num;
        
        for (int i=0;i<42;i++)
            array[i] = 0;
        
        for (int i=0;i<10;i++) {
            num = Integer.parseInt(br.readLine())%42;
            if (array[num] != 0) // 해당 나머지가 이미 세어졌는지 검사
                continue;
            else
                array[num]++;
        } // array 의 인자는 모두 0 또는 1이 된다
        
        int count = 0;
        for (int i=0;i<42;i++)
            count += array[i]; // 인자의 합 == 나머지의 가짓수
        
        System.out.println(count);
        
    }
}

메모리는 그대로, 시간은 0.004초 더 걸렸다

예상과 달리 코드 길이 말고 별 차이가 없다...ㅎ 만약 같은 나머지만 주어지는 상황이라면 차이가 날 수도 있지 않을까? 라고 생각해 본다.