[백준] 서로 다른 나머지 개수 구하기_3052_자바

 3052번 Java-서로 다른 나머지 개수 구하기

---

먼저 이 문제의 분류는 <1차원 배열>입니다. 해당 분류는 타 분류에 비해 낮은 단계에 속합니다.

그럼에도 불구하고, 이 문제를 푸는데 상당히 애먹었습니다.

결국 검색을 통해 해답을 알게 되었습니다.

놀라웠던 것은 이 문제를 푸는데 다양한 방법이 있다는 것입니다.

따라서 그 방법들을 정리하고 이해하기 위해서 이렇게 올립니다.

https://www.acmicpc.net/problem/3052

3052번: 나머지

---

1. 문제

두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0 ,2 이다.
수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

---

2. 예제

---

3. 풀이

해당 문제를 3가지 방식으로 풀어보려고 합니다.

그러기 위해서 우리는 Scanner, BufferedReader, HashSet에 대해서 알아야 합니다.

한번 문제를 풀어보며 개념을 정리해보도록 하겠습니다.

---

- 방법 1

Scanner, 기본 정규식을 활용한 문제 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    	
    	Scanner sc = new Scanner(System.in); //입력 받기 위한 스캐너 클래스
        
        int[] arr = new int[10];
        boolean bl; // 배열의 n번째 나머지와 n+1번째 나머지 동일 여부 판단 변수
        int count = 0; // 서로 다른 나머지들의 개수 변수
        
        for(int i=0; i<arr.length; i++) {
        	arr[i] = sc.nextInt()%42;
        }
        
        for(int i=0; i<arr.length; i++) {
        	bl = false; // 기본값 초기화
            for(int j=i+1; j<arr.length; j++) {
            	if(arr[i] == arr[j]) {
                	bl = true;
                    break;
                }
            }
            if(bl==false) {
            	count++;
            }
        }
        
        system.out.println(count);
	}
}

1) Scanner는 java.utill 패키지에 포함된 외부 클래스입니다. 주로 자바에서 입력을 받을 때 사용되는 스캐너 클래스입니다. 정수, 실수, 문자열을 읽을 수 있습니다. JDK1.5부터 추가되어 사용 가능합니다.

→ Scanner 사용 방법

import java.utill.Scanner;
.
.
Scanner sc = new Scanner(System.in); // Scanner 객체 생성
* 여기서 System.in은 입력한 값을 바이트 단위로 읽는 것을 뜻합니다.
int count = sc.nextInt( ); // next+자료형()
String name = sc.next( );
* nextLine( ) : 문자열 전체를 입력받는 메소드

2) 처음 반복문(for)을 통해서 배열의 길이만큼 수를 입력받습니다. 그리고 입력받은 수를 42로 나누었을 때의 나머지를 배열에 넣습니다.

3)

이중 반복문(for)을 활용하여 배열 내부의 값이 동일하지 여부를 체크합니다.
즉, 첫 번째 for문의 i 값이 0일 때 j는 i보다 1부터 9까지 반복을 합니다.
따라서 배열에서 0번째 값과 1~9에 위치한 수들을 비교하는 것인데요.
만약 값이 다르다면, 나머지 값 동일 여부 판단 변수인 bl이 false일 것입니다.
예를 들어서 1~9번째까지 동일한 수가 없다면 arr[0]의 값과 동일한 수는 어떤 위치에도 없다는 뜻입니다.
그렇다면 내부 for문은 종료가 되고 if문으로 넘어가서 count를 1 증가시킵니다.
반대로 내부 반복문을 도는 도중에 동일 값이 있다면 bl은 true가 되고 반복문을 그 시점에서 멈춥니다.
bl이 true이기 때문에 count 값도 증가하지 않습니다. 이제 첫 for문의 처음으로 돌아가고 i는 1이 됩니다.

예시 손버깅

배열에 위와 같이 나머지를 갖고 있을 때, index 3과 4는 배열에서 동일한 값이 없기 때문에 bl은 false가 되고 count는 1이 증가한다. 그리고 마지막 수는 비교할 수 있는 값이 없기 때문에 bl은 false 기본값을 유지하고 count가 1이 증가한다.

---

- 방법 2

BufferedReader를 활용한 문제 풀이

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

public class Main {
	public static void Main(String[] args) throws IOException {
 		
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[] arr = new int[10];
        boolean bl;
        int count = 0;
        
        for(int i=0; i<arr.length; i++) {
        	arr[i] = Integer.parseInt(br.readLine())%42;
        }
        
        for(int i=0; i<10; i++) {
        	bl = false;
            for(int j=i+1; j<arr.length; j++) {
            	if(arr[i] == arr[j]) {
                	bl = true;
                    break;
               	}
            }
            if(bl==false) {
            	count++
            }
        }
        System.out.println(count);
    }
}

1) 이 방법은 첫 번째 알아본 방식과 유사하나 Scanner가 아닌, BufferedReader를 통해서 입력받은 것입니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in); // 객체 생성

int num = Integer.parseInt(br.readLine());
* readLine()을 사용하면 데이터를 라인 단위로 읽습니다. 단, readLine 함수의 리턴 값은 String이므로 다른 타입으로 출력할 때는 형변환을 해줘야 합니다.

2) 여기서 포인트는 BufferedReader가 Scanner에 비해 빠른 속도로 출력한다는 것입니다. 자세하게는 뒤에서 예시를 보여드리겠습니다.

---

- 방법 3

BufferedReader와 HashSet을 활용한 문제 풀이

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

public class Main {
	Public static void main(String[] args) throws IOException {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Integer> hs = new HashSet<Integer>();
        
        for(int i=0; i<10; i++) {
        	hs.add(Integer.parseInt(br.readLine()) % 42);
            //입력받은 값의 나머지 값을 add메소드를 통해 HashSet에 저장
        }
        br.close();
        System.out.print(hs.size());
    }
}

1) HashSet은 Set 인터페이스의 구현 클래스입니다. Set은 객체들 중복해서 저장할 수 없고, 하나의 null 값만 저장할 수 있습니다. 또한 저장 순서는 유지되지 않습니다.

2) HashSet은 add(value) 메소드를 통해서 값을 추가합니다. 만약 내부에 value와 동일한 값이 없다면 value를 HashSet에 집어넣고 true를 반환합니다. 반대로 동일한 값이 존재한다면 false를 반환합니다.

3) HashSet의 size() 메소드를 통해 HashSet 크기를 구합니다.

4) 세 번째 방법은 HashSet의 성질과 메소드를 활용해서 문제를 푼 방법입니다. 

 

---

4. 결론

이 문제에서 제시한 '서로 다른 나머지의 개수'는 '배열 내의 중복된 수를 제거하고, 배열의 크기를 출력하라'라고 해석할 수 있습니다.

위 같이 3가지 방법은 모두 정답입니다. 하지만 속도와 메모리의 차이를 갖습니다.

• 제출 번호 38347122 : HashSet, Scanner
• 제출 번호 38347016 : HashSet, BufferedReader
• 제출 번호 38345968 : 배열, BufferedReader
• 제출 번호 38344221 : 배열, Scanner

시간을 비교했을 때, BufferedReader를 활용했을 때 확실하게 감소한 것이 보입니다.