[class 1]백준 나머지(3052번) 풀이 (C++/Python)

문제 : 나머지(3052번)(Bronze II)

문제 링크 : https://www.acmicpc.net/problem/3052
출처 : Baekjoon Online Judge

 

이 문제는 원래 HashSet 혹은 HashMap을 사용해서 해결해야 하는 문제입니다.

하지만 이 문제는 class 2가 아닌 class 1이며 해당 문제를 곰곰히 생각해보니 굳이 HashSet 혹은 HashMap을 사용할 이유가 없습니다.

왜냐면 결국 나누기 42 해서 나오는 나머지 경우의 수가 42개 뿐이며 이것은 배열만으로 구현할 수 있거든요.

bool check[42];

예시로 나머지가 1, 2, 3, 4, 5, 6, 7, 8, 9, 1이라고 가정합니다.

그러면 check[1]부터 check[9]까지 모두 true로 바뀌게 되며 1이 한 번 더 등장해도 이미 true 처리되어 중복 연산을 방지할 수 있습니다.

이건 사실 내부적으로 보면 LinkedList에서 이미 존재한 원소가 있으면 원소 추가를 진행하지 않는 것과 같습니다.

(실제 Hash Table은 ArrayList + LinkedList 조합이거든요.)

그래서 사실상 이 문제는 본격적인 집합과 맵 들어가기 전 손풀기 문제입니다.

집합과 맵은 class 2에서 다루도록 하겠습니다.

 

이제 배열만으로 해당 문제를 해결하도록 하겠습니다.

[C++]

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

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

    bool check[42];
    for(int i = 0; i < 42; i++) check[i] = false;

    for(int i = 0; i < 10; i++) {
        int n;
        cin >> n;
        check[n % 42] = true;
    }

    int result = 0;
    for(int i = 0; i < 42; i++) {
        if(check[i]) result++;
    }

    cout << result;

    return 0;
}

이미 true가 된 곳에 중복 원소가 오면 result++ 되지 않고 그냥 무시됩니다.

조심해야 할 것은 반드시 check[n % 42] = true;로 해주세요.

제가 check[n] = true;로 하다가 오답 받았습니다.

[Python]

import sys

input = sys.stdin.readline

check:list = [False for _ in range(42)]

for _ in range(10) :
    check[int(input().rstrip()) % 42] = True
    
print(sum(check))

JavaScript와 Python는 truthy한 값들을 1로 취급해서 sum(check)에서 true -> 1 취급하여 true의 개수를 출력하는 방식을 채택했습니다.