백준 Java) 3052번 나머지 문제

일단 문제를 한번 보자!

 

www.acmicpc.net/problem/3052

3052번: 나머지

10개의 수를 받아 42로 나눈 나머지 값을 서로 다른 값이 몇 개가 있는지 구하는 것이다.

필자는 선택 정렬로 구현해보면 어떨까?라는 생각으로 풀어보았다. 

처음 접근한 방식을 써보겠다.

import java.util.Scanner;

public class main {
	public static void main(String[] args) {
		int[] num = new int[10];
		Scanner sc = new Scanner(System.in);
		int a = 42;
		int count = 10;
		
		for(int i=0; i<10;i++) {
			 int n = sc.nextInt();
			 num[i] = n%a;
		}
		for(int i=0;i<num.length;i++) {
			for(int j=i+1;j<num.length;j++) {
				if(num[i] == num[j]) {
					continue;
				}
				else {
					count++;
				}
			}
		}
		
		System.out.print(count);
		
	}
}

 

선택정렬로 각각 요소마다 비교해서 값을 카운터 하려고 했는데 사실 여기서 문제가 생겼었다. 100번을 비교한다는 것! 

중복된 값이 여러번 체크되면서 이 방법으로는 맞지 않아서 다시 접근해보기로 했다.

import java.util.Scanner;

public class main {
	public static void main(String[] args) {
		int[] num = new int[10];
		int[] number = new int[42];
		Scanner sc = new Scanner(System.in);
		int a = 42;
		int count=0;
		
		for(int i=0; i<10;i++) {
			 int n = sc.nextInt();
			 num[i] = n%a;
		}
		
		for(int i=0;i<num.length;i++) {
			number[num[i]]++;
		}
		for(int i=0;i<number.length;i++) {
			if(number[i]!=0 ) {
				count++;
			}
		}
		
		System.out.print(count);
		
	}
}

어차피 10개라는 한정적인 숫자와 42로 나눈 나머지 값이니까. 최대 숫자가 42일 것이다. 그래서 메모리 측면에서 할당되지 않은 값도 공간을 만들어주어 비효율적이다. 보면 num이라는 배열은 사용자가 10개의 숫자를 42로 나눈 나머지 값을 넣어준다. 그리고 number는 42개의 공간을 만들어준다. 자바에서는 int형 배열을 선언하면 모든 값을 0으로 초기화시켜주는 점을 이용했다. 이제 이 num 값을 number의 num값 배열 안에 넣어줘 1씩 증가시켜준다. 그러면 만약 값이 있으면 1 없으면 0이 된다. 마지막으로 number를 전체 순회하여 1인 값이 있으면 count에 1씩 증가시켜준다. 그럼 그 토털 값이 바로 서로 다른 나머지 값의 수가 된다. 문제는 쉽지만 어떻게 접근하느냐에 따라 다른 것 같다. hashset을 이용하여 푸는 방식도 있다. 아무튼 풀긴 풀었다.... 끝!