백준-1차원 배열 3052 나머지

3052번: 나머지 (acmicpc.net)

 

수를 10개 입력받은 뒤, 42로 나눈 나머지를 구해, 서로 다른 값이 몇 개 있는지를 출력

풀이 방법은 두가지가 있다. 이전 문제처럼 고정사이즈 배열에 초기화 값을 통해 제어할 지 아니면 벡터를 통해 중복값을 제외하고 푸시로 밀어넣을지 벡터를 통한 방법은 매 입력 회차마다 벡터를 순회해봐야 된다는 단점이 있지만 사이즈 출력때 순회가 없다.

 

시간 복잡도는 

1.  고정사이즈 배열 초기화 => N

2. 벡터를 통한 중복값 제어 => N**2

지금은 INPUT의 횟수가 10, 나누는 값이 42로 매우 작아 별로 차이가 나지 않지만 만약 나누는 값이 조금만 커진다면 벡터를 통한 순회는 시간복잡도가 기하급수적으로 늘어나므로 1번을 통해 문제를 풀어야 한다.

제약사항

• 0 <= INPUT <= 1,000

주의 사항

0도 정수다.

C 풀이

나머지_3052.c

/**
* 백준 1차원 배열 3052 나머지
* 수를 10개 입력받은 뒤, 42로 나눈 나머지를 구해, 서로 다른 값이 몇 개 있는지를 출력
* 풀이 방법은 두가지가 있다. 이전 문제처럼 고정사이즈 배열에 초기화 값을 통해 제어할 지 아니면 벡터를 통해 중복값을 제외하고 푸시로 밀어넣을지 벡터를 통한 방법은 매 입력 회차마다 벡터를 순회해봐야 된다는 단점이 있지만 사이즈 출력때 순회가 없다.

* 시간 복잡도는 
* 1.  고정사이즈 배열 초기화 => 2N
* 2. 벡터를 통한 중복값 제어 => N**2
* 지금은 INPUT의 횟수가 10, 나누는 값이 42로 매우 작아 별로 차이가 나지 않지만 만약 나누는 값이 조금만 커진다면 벡터를 통한 순회는 시간복잡도가 기하급수적으로 늘어나므로 1번을 통해 문제를 풀어야 한다.
*
* 제한사항
*****************************************
* 0 <= INPUT <= 1,000                   *
*****************************************
*
*
*
* 주의
* 0도 정수다.
* 
*
* 풀이시간 5분
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void)
{
    int cnt = 0;
	int res[42] = {0};

    for (int i = 0; i < 10; ++i)
    {
        int N;
        scanf("%d", &N);
        ++res[N % 42];
    }

    for (int i = 0; i < 42; ++i)
    {
        if (res[i] != 0)
        {
            ++cnt;
        }
    }
    printf("%d", cnt);
    return 0;
}

C++ 풀이

나머지_3052.cpp

/**
* 백준 1차원 배열 3052 나머지
* 수를 10개 입력받은 뒤, 42로 나눈 나머지를 구해, 서로 다른 값이 몇 개 있는지를 출력
* 풀이 방법은 두가지가 있다. 이전 문제처럼 고정사이즈 배열에 초기화 값을 통해 제어할 지 아니면 벡터를 통해 중복값을 제외하고 푸시로 밀어넣을지 벡터를 통한 방법은 매 입력 회차마다 벡터를 순회해봐야 된다는 단점이 있지만 사이즈 출력때 순회가 없다.

* 시간 복잡도는 
* 1.  고정사이즈 배열 초기화 => 2N
* 2. 벡터를 통한 중복값 제어 => N**2
* 지금은 INPUT의 횟수가 10, 나누는 값이 42로 매우 작아 별로 차이가 나지 않지만 만약 나누는 값이 조금만 커진다면 벡터를 통한 순회는 시간복잡도가 기하급수적으로 늘어나므로 1번을 통해 문제를 풀어야 한다.
*
* 제한사항
*****************************************
* 0 <= INPUT <= 1,000                   *
*****************************************
*
*
*
* 주의
* 0도 정수다.
* 
*
* 풀이시간 5분
*/

#include <iostream>
#include <vector>

using namespace std;

int main() 
{
    int N, cnt = 0;
    
    vector<int> arr;

    for (int i = 0; i < 10; ++i)
    {
        cin >> N;
        N %= 42;

        bool isExists = false;
        for (int j = 0; j < arr.size(); ++j)
        {
            if (arr[j] == N)
            {
                isExists = !isExists;
                break;
            }
        }
        if (isExists == 0)
        {
            arr.push_back(N);
        }
    }

    cout << arr.size() << '\n';
    return 0;
}

 

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace