[백준] 3052 나머지

- 코드 문제점 분석

1. 서로 다른 나머지를 찾는 방식이 잘못되었다.

• arr[i] % 42 != arr[0] % 42 -> 이 조건은 모든 값이 arr[0]의 나머지와 다를 때만 카운트 된다.
• 예를 들어, arr[0]의 나머지가 5라면, 5와 다른 나머지만 세기 때문에 중복된 값이 있어도 고려되지 않는다.
• Set을 사용하여 중복을 자동 제거한다.

2. count 변수 활용 오류

• 현재 count는 나머지가 arr[0]과 다른 경우에만 증가한다.
• 필요한 것은 서로 다른 나머지의 개수이다.
• Set을 사용하여 중복을 제거한 후 크기를 출력한다.

 

- 잘못된 코드

package CLASS1; import java.util.Scanner; public class 나머지 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int[] arr = new int[10];         for(int i = 0; i < 10; i++) {             arr[i] = sc.nextInt();         }         int count = 0;         for(int i = 0; i < 10; i++) {             if(arr[i] % 42 != arr[0] % 42) {                 count++;             }         }         System.out.print(count);         sc.close();     }     }

 

 

- 수정된 코드

package CLASS1; import java.util.Scanner; import java.util.HashSet; public class 나머지 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         HashSet<Integer> modSet = new HashSet<>(); // 중복을 방지하는 Set 사용         for (int i = 0; i < 10; i++) {             int num = sc.nextInt();             modSet.add(num % 42); // 42로 나눈 나머지를 Set에 저장         }         System.out.println(modSet.size()); // 서로 다른 나머지 개수 출력         sc.close();     }     }

 

 

- 설명

1. HashSet<Integer>를 사용하였다.

• Set은 중복을 허용하지 않는다. -> 중복된 나머지는 자동으로 제거된다.

2. 10개의 정수를 입력받고, 42로 나눈 나머지를 Set에 추가한다.

• modSet.add(num % 42);

3. 서로 다른 나머지 개수를 modSet.size()로 출력한다.

• System.out.println(modSet.size());

 

- Set을 사용해야 하는 이유

방법	문제점	해결 방법
if(arr[i] % 42 != arr[0] % 42)	특정 값과 비교하는 방식이라 모든 값을 고려하지 못함	Set을 사용하여 중복을 자동 제거
배열을 정렬 후 중복 제거	추가적인 연산 (O(N log N))이 필요	HashSet 사용 시 O(N)으로 빠르게 해결