[2577 :JAVA] 1차원 배열 > 나머지 (hashset)

[백준알고리즘: 1차원 배열 단계 > 4. 나머지] - JAVA

 

문제

두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지 이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0, 2이다.

수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다.

 

출력

첫째 줄에, 42로 나누었을 때, 서로 다른 나머지가 몇 개 있는지 출력한다.

 

 

 

 

[풀이 방법]

 

먼저 for문을 이용하여 배열에 10개의 입력 값을 42로 나눈 나머지 값을 삽입한다.

그 다음 다른 for문을 이용해 배열의 값을 비교한다.

 

이 때, i와 k의 값을 끊임없이 비교하여 cnt가 81이 되는 문제가 발생했다.

이 문제를 해결하기 위해서 고민하던 중 중복 검색을 방지하기 위해 break를 이용하여 문제를 해결할 수 있었다.

* break: 반복문에서 break를 사용하면 반복문에서 빠져나갈 수 있다. (일반적으로 for문보다는 while문에서 많이 사용하여 for문에서는 사용하지 않는다고 생각했었다.)

package com.algorithm.chapter5;

import java.util.Scanner;

public class ch5_4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] num = new int[10];
        int cnt = 0;

        // 배열에 값 넣기
        for(int j=0; j<num.length; j++){
            num[j] = sc.nextInt() % 42;
        }

        // 42로 나눈 후 값을 비교
        for (int i=0; i<num.length; i++){
            for(int k=0; k<num.length; k++){
                if(num[i] != num[k]){
                    cnt++;
                    // 중복으로 확인할 필요 없으니 cnt++ 후 종료
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

 

 

정답을 제출한 후 코드를 천천히 살펴보았다.

위 코드가 매우 지저분한 코드는 아니라고 생각했지만 분명히 이것보다는 간단한 방법이 있을 것이라고 판단하여 구글을 통해 검색을 진행했다.

 

 

 

hashset을 이용하면 간단하게 해결할 수 있다는 사실을 알 수 있었다.

 

* HashSet

- Set 인터페이스에서 지원하는 구현 클래스.

- 순서대로 입력되지 않고 일정하게 유지된다.

- null을 포함할 수 있다.

- 중복을 허용하지 않는다.

- 사용 방법은 아래와 같다.

// 초기화 및 선언
HashSet<Integer> setInt = new HashSet<Integer>();
HashSet<String> setString = new HashSet<String>();

// 값 삽입
setInt.add(number);

> HashSet은 중복을 허용하지 않기 때문에 값을 HashSet에 저장하여 서로 다른 나머지 값의 개수를 쉽게 구할 수 있다.

 

위의 정의를 토대로 HashSet을 이용하여 코드를 작성했다.

1) 기존의 코드와 달리 배열을 이용하지 않아도 되기 때문에 for문을 이용하여 10개의 값을 HashSet에 직접 삽입한다.

2) HashSet에 값을 삽입할 때 %42 수식을 이용하여 나머지 값을 저장한다.

3) HashSet은 중복 값을 허용하지 않는다. 따라서 저장된 값은 모두 서로 다른 나머지 값이다.

　HashSet의 size는 중복되지 않은 서로 다른 나머지 값의 개수를 의미한다.

 

public class ch5_4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashSet<Integer> setInt = new HashSet<Integer>();

        for (int i=0; i<10; i++){
            // 입력받은 값을 배열을 이용하지 않고 직접 삽입한다.
            // 42로 나눈 나머지 값을 HashSet에 바로 저장한다.
            setInt.add(sc.nextInt() % 42);
        }
        System.out.println(setInt.size());
    }
}

 

 

끝.