[BaekJoon] #3052 - 나머지 [Java][C++]

문제 링크

---

1. 아이디어

42로 나눈 겹치지 않는 나머지의 개수를 구하는 문제로 방문 체크 배열을 활용해서 해결할 수도 있고, 집합 자료구조를 활용해도 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
방문 체크	$O(1)$	$O(1)$
해시셋	$O(1)$	$O(1)$

---

3. 코드

풀이 1: 방문 체크 [Java][C++]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        boolean[] seen = new boolean[42];
        for (int i = 0; i < 10; i++) {
            int x = Integer.parseInt(br.readLine());
            seen[x % 42] = true;
        }

        int cnt = 0;
        for (boolean flag : seen) {
            if (flag) cnt++;
        }

        System.out.println(cnt);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<bool> seen(42);
    for (int i = 0; i < 10; i++) {
        int x;
        cin >> x;
        seen[x % 42] = true;
    }

    cout << count(seen.begin(), seen.end(), true);
}

---

풀이 2: 해시셋 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Set<Integer> seen = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            int x = Integer.parseInt(br.readLine());
            seen.add(x % 42);
        }

        System.out.println(seen.size());
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    unordered_set<int> seen;
    for (int i = 0; i < 10; i++) {
        int x;
        cin >> x;
        seen.insert(x % 42);
    }

    cout << seen.size();
}

---