[백준] ✔️3052 나머지 (설명/코드/정답)

문제 링크 : https://www.acmicpc.net/problem/3052

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 128  MB

 

입력받은  10개의 수를 42로 나눈 나머지가 총 몇 개인지 구하는 프로그램 작성 

숫자는 1,000보다 작거나 같고, 음이 아닌 정수

 

 

2. 설계/검증 

 

복잡도

시간 복잡도	최악의 경우	공간 복잡도
O(1)		O(1)

 

 

 

 

3. 정상 코드

 

- 배열 풀이

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        // 입력 받은 자연수 저장할 배열
        int[] nums = new int[10];
        for (int i = 0; i < 10; i++) {
            nums[i] = scan.nextInt();
            // 유효성 검사
            if (nums[i] < 0 || nums[i] > 1000) {
                System.out.println("1,000보다 작거나 같고, 음이 아닌 정수");
                return;
            }
        }

        // 나머지를 저장할 배열
        boolean[] remainders = new boolean[42]; // 42로 나눈 나머지는 0~41
        // 나머지 계산 
        for (int i = 0; i < 10; i++) {
            remainders[nums[i] % 42] = true;
        }
        // 나머지 존재만 세기 
        int count = 0;
        for (boolean remainder : remainders) {
            if (remainder) {
                count++;
            }
        }

        // 결과 출력
        System.out.println(count);

        scan.close();
    }
}

 

 

- set 풀이

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

public class Main {

    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        Set<Integer> remainder =new HashSet();

        for (int i = 0; i < 10; i++) {

            remainder.add(scan.nextInt() % 42);

        }
        System.out.println(remainder.size());
        scan.close();
    }
}

 

 

 

 

추가 정리

 

Set의 특징

• 중복을 허용하지 않음: Set에 같은 요소를 두 번 추가하려고 하면, 한 번만 저장됩니다.
• 순서가 없음: Set은 요소의 순서를 유지하지 않습니다. (단, LinkedHashSet은 순서를 유지합니다.)
• 빠른 검색: 일반적으로 검색, 삽입, 삭제가 빠릅니다.

 

 

Set과 배열 비교

• 중복 허용 여부: 배열은 중복된 요소를 허용하지만, Set은 중복된 요소를 허용하지 않습니다
• 순서: 배열은 요소의 순서를 유지하지만, Set은 순서를 유지하지 않습니다. (단, LinkedHashSet은 예외)
• 검색 성능: Set은 일반적으로 빠른 검색 성능을 제공하며, 배열은 선형 검색을 필요로 하므로 상대적으로 느립니다.

Set은 특히 중복된 데이터를 제거하거나 집합 연산을 수행할 때 유용합니다. Java의 다양한 Set 구현 클래스를 이해하고 상황에 맞게 적절히 사용하면 더욱 효율적인 프로그래밍을 할 수 있습니다.