[백준] [알고리즘 3052번: 나머지] JAVA

나머지 

문제

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

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

입력

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

출력

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

예제 입력 1 복사

1
2
3
4
5
6
7
8
9
10

예제 출력 1 복사

10

각 수를 42로 나눈 나머지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이다.

예제 입력 2 복사

42
84
252
420
840
126
42
84
420
126

예제 출력 2 복사

1

모든 수를 42로 나눈 나머지는 0이다.

예제 입력 3 복사

39
40
41
42
43
44
82
83
84
85

예제 출력 3 복사

6

각 수를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 6개가 있다.

 

풀이

============================================================================================

이 문제는 HASH SET을 알고 있는지 묻는 문제이다. 

사실상 Hash set을 알면 쉽게 풀고 모르면 복잡해지는데 출제 의도대로 hash set을 이용하여 문제를 풀어보도록 하자.

 

기본적으로 hash set은 중복은 취급하지 않는다.

 

고로 이미 있는 값을 중복적으로 저장하려고 하면?

 

그말은 hast set에 있는 값들은 중복이 아닌 고유한 값이라는 의미이다.

 

지금 이 문제가 요구하는 것이 서로 다른 값인데 그 말은 결국 다르게 말하면

고유한 값이 몇개가 있는지 묻는 것이다. 

 

 

그렇다면 hash set에 저장을 하고 그 크기를 출력하면 ? 간단하게 풀린다는 것이다. 

 

 Hash set을 소환하는 방법은 다음과 같다. 

HashSet<Integer> h = new HashSet();

 반복문을 통해 입력한 값을 42로 나누고 나머지 값을 Hash set에 넣어주는 과정은 다음과 같다.

for (int i = 0; i < 10; i++) {
  h.add(Integer.parseInt(br.readLine()) % 42);
}

Hash set의 크기를 출력하는 것은 다음과 같다.

System.out.print(h.size());

전체코드! 

import java.util.HashSet;
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));
    HashSet<Integer> h = new HashSet();

    for (int i = 0; i < 10; i++) {
      h.add(Integer.parseInt(br.readLine()) % 42);
    }
    br.close();
    System.out.print(h.size());
  }
}

참..쉽죠?