[백준알고리즘/1차원 배열] 3052번 문제 : 나머지(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 4단계 3052번 나머지를 풀어봤습니다

이번 문제는 다양한 방식으로 풀 수 있는 문제입니다

저는 총 3가지 방식으로 풀었습니다

그 방법에 대해서 설명하겠습니다!

---

문제

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

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

 

입력

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

 

출력

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

 

 

---

 

문제 풀이

첫 번째 풀이 방식입니다

1. 반복문을 사용 42로 나눈 나머지값을 배열 변수 rest를 선언하고 데이터를 넣습니다

2. Arrays.sort를 사용해 rest을 정렬합니다

3. 반복문을 사용해 rest[i - 1] != rest[i] 가 같지 않으면 나머지가 다른 것으로 판단 Count를 1 더해줍니다

4. 결과 출력

제일 무난한 풀이 방법이라 생각합니다

Arrays.sort를 응용해서 문제를 풀었습니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// 1. 반복문을 사용 42로 나눈 나머지값을 배열 변수에 넣는다.
		// BufferedReader 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 입력 배열 선언
		int rest[] = new int[10];
		
		// 반복문으로 42의 나머지 값을 배열에 순차적으로 넣는다.
		for(int i = 0; i < 10; i++)
		{
			rest[i] = Integer.parseInt(br.readLine()) % 42;
		}
		
		// 2. Arrays.sort로 나머지 값 정렬
		Arrays.sort(rest);
		
		// 3. 반복문을 사용해 i != i - 1인 경우 Count++
		int Count = 1;

		// 반복문을 사용해 다른 나머지를 Count한다.
		for(int i = 1; i < 10; i++)
		{
			if(rest[i - 1] != rest[i])
			{
				Count++;
			}
		}
		
		// 4. 결과 출력
		System.out.print(Count);
	}
}

 

---

두 번째 풀이 방식입니다

1. 반복문을 사용 42로 나눈 나머지값을 배열 변수 array를 선언하고 데이터를 넣습니다

2. 사이즈가 42개인 배열 변수를 rest를 선언합니다

3. rest[array[i]]++를 사용해서 나머지값을 rest에 밀어넣습니다

4. 반복문을 사용해 rest[i]가 0보다 큰 값이 있으면 count++ 합니다

5. 결과 출력

사이즈가 42인 배열을 만들어서 나머지값을 배열 사이즈에 맞춰서 넣어줘서 구하는 방식입니다

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

public class Main{
    public static void main(String[] args) throws IOException{
		// 1. 반복문을 사용 42로 나눈 나머지값을 배열 변수에 넣는다.
		// BufferedReader 선언
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        

		// 입력 배열 array 선언
        int[] array = new int[10];

		// 반복문으로 42의 나머지 값을 배열에 순차적으로 넣는다.
        for(int i = 0; i < 10; i++)
        {
        	array[i] = Integer.parseInt(br.readLine()) % 42;
        }

        // 2. 나머지 배열 rest 선언
        int[] rest = new int[42];
        
        // 3. array를 rest에 밀어넣는다
        for(int i = 0; i < 10; i++)
        {
        	rest[array[i]]++;
        }
        
        // 4. 반복문을 사용해 rest[i]가 0보다 크면 count++
        int count = 0;        
        for(int i = 0; i < 42; i++)
        {
        	if(rest[i] > 0)
        		count++;
        }
        
        // 5. 결과 출력
        System.out.print(count);
    }
}

 

---

세 번째 풀이 방식입니다

1. 반복문을 사용 42로 나눈 값을 HashSet에 추가

 -> HashSet은 같은 값이 들어오면 내부에 저장하지 않고 넘어갑니다

2. 결과 출력

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

public class Main{
    public static void main(String[] args) throws IOException{
		// BufferedReader 선언
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // HashSet 변수 선언
        HashSet<Integer> set = new HashSet<>();
        
        // 1. 반복문을 사용 42로 나눈 나머지 값을 HashSet에 추가
        // HashSet은 같은 값이 들어오면 내부에 저장하지 않고 넘어갑니다
        for(int i=0; i<10; i++){
            set.add(Integer.parseInt(br.readLine())%42);
        }
        
        // 2. 결과 출력
        System.out.print(set.size());
    }
}

 

---

속도 비교

세 가지 방식으로 풀어봤으니 위 세 가지 방식의 메모리 및 속도를 확인해보겠습니다!

세 가지 풀이 방식대로 차례대로 결과값입니다

HashSet방식으로 풀었을 때 시간이 제일 빠르네요

두 개의 배열을 선언해서 구했을 때가 메모리가 제일 적게드네요

 

여기까지 백준알고리즘 3052번 나머지를 풀은 내용이었습니다

이 글이 알고리즘을 공부하는 분들께 도움이 되었으면 좋겠습니다!

 

다음 문제 : 2021.05.05 - [알고리즘/알고리즘JAVA] - [백준알고리즘/1차원 배열] 1546번 문제 : 평균

이전 문제 : 2021.05.03 - [알고리즘/알고리즘JAVA] - [백준알고리즘/1차원 배열] 2477번 문제 : 숫자의 개수(자바/JAVA)