[자바, C++] 백준 3052 - 나머지 (java cpp)

 문제 : boj3052

---

 

필요 알고리즘 개념

• 사칙연산, 구현, 해시
  
  • 나머지 연산을 어떻게 구하는지 알고 있어야 한다. 기본적으론 배열을 이용해 그냥 구현으로 풀 수 있으나, 해시를 사용해서도 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  코드에서 나머지연산은 '%'를 사용한다. (자바, c++ 둘 다)

 

풀이 1 : 해시 사용

  10개의 입력을 받으면서 42로 나눈 뒤 나머지를 HashSet에 넣는다. 해시셋은 중복값을 가질 수 없으므로 HashSet의 size가 결국 답이다. (자바 코드는 풀이 1로 풀었다.)

 

풀이 2 : 배열 사용

  42로 나눈 나머지는 항상 0이상 41이하의 값을 가진다. 따라서 42칸의 배열을 사용하면 나머지가 나온 경우를 파악할 수 있다. tmp에 입력을 받았고, 42칸짜리 배열이 arr라고 한다면 arr[tmp%42]++ 를 해주면 된다. 혹은 어차피 존재하는지만 알면 되므로 arr[tmp%42] = 1로 해줘도 마찬가지다.

 

  이후 0부터 41까지의 인덱스에 대해 에서 0이 아닌 값의 수를 세면 된다. c++의 경우 0은 false, 그 이외는 true를 나타내므로 cnt += arr[i]?1:0; 와 같이 처리해주면 된다. (C++ 코드는 풀이 2로 풀었다.)

 

---

 

코드(Java) : github

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

public class Main {	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		HashSet<Integer> hs = new HashSet<Integer>();
		
		for (int i = 0; i < 10; i++) {
			int tmp = Integer.parseInt(br.readLine()) % 42;
			if (!hs.contains(tmp))
				hs.add(tmp);
		}
		
		bw.write(hs.size() + "\n");
		bw.flush();		
		bw.close();
		br.close();
	}
}

 

 

코드(C++) : github

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 10, tmp;
    int arr[42] = {0,};
    while (n--) {
        cin >> tmp;
        arr[tmp%42]++;
    }
    int cnt = 0;
    for (int i = 0; i < 42; i++) {
        cnt += arr[i]?1:0;
    }
    cout << cnt;
}