[백준] 3052번 : 나머지 - JAVA [자바]

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

3052번: 나머지

 

 

---

• 문제

 

 

 

매우 간단한 문제다!

 

 

 

 

 

---

• 2가지 풀이방법을 제시한다

이 문제는 우리가 흔히 쓰는 배열을 써서 풀어도 되지만 사실 hashset 을 쓰면 더욱 쉽고 간단하게 풀 수 있다. 그래서 먼저 가장 기본적인 방법인 HashSet 을 이용하는 방법을 보여드릴것이다.

그 다음 방법으로 배열을 이용하는 방법을 보여드릴것이다.

 

 

---

• HashSet

HashSet 은 자바 Collection 중 Set 의 파생클래스이다.

 

set 을 집합이라고 생각하면 되는데, HashSet 의 경우 몇 가지 특징이 있다.

 

1. 중복되는 원소를 넣을 경우 하나만 저장한다. 즉, 중복원소를 허용하지 않는다.
2. HashSet 은 순서 개념이 없다. 따라서 Collections.sort() 메소드를 사용할 수 없다. 만약 정렬을 하고 싶다면 리스트로 변환 후 정렬해야한다.

 

이 문제에서는 결국 나머지 값에서 "서로 다른" 개수를  세면 되는 것이기 때문에 HashSet 을 이용하면 자연스럽게 나머지 값이 HashSet 원소에 이미 저장되어있어 중복일 경우 저장이 되지 않고 HashSet 에 없으면 저장한다.

즉, HashSet 에 저장하면서 들어간 원소의 개수가 HashSet 의 사이즈가 되는 것이고, 이는 결국 "서로 다른 나머지"가 되는 것이다.

 

 

 

---

• 풀이

- 방법 1 

import java.util.Scanner;
import java.util.HashSet;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		HashSet<Integer> h = new HashSet<Integer>();

		for (int i = 0; i < 10; i++) {
			h.add(in.nextInt() % 42);
		//입력받은 값의 나머지 값을 add메소드를 통해 HashSet에 저장
		}
        
		in.close();
		System.out.print(h.size());
	}
}

HashSet.add() 메소드는 HashSet에 저장하는 메소드이다. 처음 생성할 때 HashSet<Integer> 으로 타입을 Integer로 선언했기 때문에 int 형 또는 Integer 객체를 넣어주어야한다.

또한 이 메소드에서 값을 넣을 때 만약 중복되는 값이 없으면 HashSet 에 저장되면서 True 를 반환하고, 만약 중복되어 저장되지 않으면 False 를 반환한다.

 

또한 HashSet.size() 는 HashSet 의 크기(= 저장되어 있는 원소의 개수)를 반환한다.

 

 

---

 

또한 시간을 단축시키기 위해 입력방법을 Scanner 대신 BufferedReader 로 바꾸면 다음 코드와 같이 된다.

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<Integer>();

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

 

 

---

- 방법 2 

 

앞서 배열을 이용할 수도 있다고 했다.

 

기본적인 방법은 나머지가 나올 수 있는 수는 0~41 이므로 길이가 42 인 boolean 배열을 생성한다.

(참고로 boolean 배열의 default 값은 false 이다.)

 

그리고 입력받은 값의 %42 을 통한 나머지 값의 index 을 true 로 바꾸어 준 뒤, 입력이 종료되면 true 값인 배열원소의 개수를 세어준다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        boolean[] arr = new boolean[42];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for(int i = 0 ; i < 10 ; i++) {
            arr[Integer.parseInt(br.readLine()) % 42] = true;
        }
        
        int count = 0;
        for(boolean value : arr) {
            if(value){    // value 가 true 라면
                count++;
            }
        }
        System.out.println(count);
    }
}

 

위와 같이 배열을 이용하여 해결 할 수도 있다.

 

 

 

 

 

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 18094478  -  BufferedReader + 배열 

채점 번호 : 18094467  -  BufferedReader + HashSet

채점 번호 : 18094459  -  Scanner + HashSet

 

 

보면 알 수 있겠지만 Scanner 가 확실히 느리고 메모리를 많이 잡아먹는다.

알고리즘 상으로는 큰 차이는 없으니 독자분들이 자신한테 맞는 알고리즘을 선택하면 되겠다.

 

 

 

---

• 정리

배열(Array)과 집합(Set)을 이용한 방법을 알아보았다.

 

특히 자바 Collecetion의 종류들은 자료구조나 알고리즘에서 많이 쓰이므로 익혀두는 것은 자바에서 필수다. 그러니 만약 여유가 된다면 Collection 종류를 검색해보는 것을 추천한다.