알고리즘 (6월 22일)

1. 문제 (배열내에서 소수 찾기)

 

---

2. 생각

1. 배열내에서 시작점과 방향, 길이를 정의하고, for문을 이용하여 모든 경우에 대해서 생각한다.
2. getDigit 메소드에 시작점(x, y)와 방향(dir), 길이(length)를 actual parameter로 전달하면 switch-case 문을 이용하여 방향(dir)의 값에 따른 다음 원소의 위치값(newX, newY)를 얻는다.
3. 만약 다음 원소가 배열 밖을 벗어나면 -1을 return하여 다음 경우에 대해서 생각한다.
4. 배열내에 존재한다면 해당 위치의 원소값을 반환한다.
5. computeValue 메소드내에서 getDigit 메소드를 통해 얻은 다음 원소들을 하나의 숫자로 합치는 과정을 수행한다.
6. 연속된 원소들로 이루어진 숫자를 main에 반환한다.
7. isPrim 메소드를 통해 해당 원소가 소수인지 판별하고, 소수이면 prim 리스트에 저장한다.
8. prim 리스트를 출력한다.

---

3. 풀이 및 코드 분석

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Comparator;

public class program {
	public static boolean isPrim(int value) {
		for(int i=2; i*i<=value; i++)
			if(value%i==0)
				return false;
		
		return true;
	}
	
	public static int getDigit(int[][] array2d, int x, int y, int dir, int k) {
		int newX = x, newY = y;
		int size = array2d.length;
		
		switch(dir) {
		case 0:newY -= k; break;
		case 1:newY -= k; newX += k; break;
		case 2:newX += k; break;
		case 3:newY += k; newX += k; break;
		case 4:newY += k; break;
		case 5:newY += k; newX -= k; break;
		case 6:newX -= k; break;
		case 7:newX -= k; newY -= k; break;	
		}
		
		if(newX<0 || newX>=size || newY<0 || newY>=size)
			return -1;
		
		return array2d[newX][newY];
	}
	
	public static int computeValue(int[][] array2d, int x, int y, int dir, int len) {
		int value=0;
		
		for(int i=0; i<=len; i++) {
			// 배열 원소 값 얻기
			int digit = getDigit(array2d, x, y, dir, i);
			
			if(digit==-1)
				return -1;
			value = value*10+digit;
		}	
		return value;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		ArrayList<Integer> prim = new ArrayList<>();
		
		// 사이즈 입력 & 배열 초기화
		System.out.print("사이즈 입력:");
		int size = scan.nextInt();
		int[][] array2d = new int[size][size];
		
		// 배열 원소 입력
		for(int i=0; i<size; i++)
			for(int j=0; j<size; j++)
				array2d[i][j] = scan.nextInt();
		scan.close();
		
		// 가능한 배열 찾아 소수인지 판별
		for(int x=0; x<size; x++) {
			for(int y=0; y<size; y++) {
				for(int dir=0; dir<8; dir++) {
					for(int length=0; length<=size; length++) {
						int value = computeValue(array2d, x, y, dir, length);
						
						if(value!=-1&&isPrim(value)&&value!=1&&(prim.contains(value)==false)&&value!=0)
							prim.add(value);
					}
				}
			}
		}
		
		// 결과 출력
		prim.sort(Comparator.naturalOrder());
		System.out.println("가능한 소수는 다음과 같습니다.");
		for(int i=0; i<prim.size(); i++)
			System.out.printf("수소[%d] = %d\n", i, prim.get(i));
	}
}

---

4. 다른 풀이

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Comparator;

public class program {
	static int[][] array2d;
	static int[] offsetX = {0, 1, 1, 1, 0, -1, -1, -1, -1};
	static int[] offsetY = {-1, -1, 0, 1, 1, 1, 0, -1};
	
	public static boolean isPrim(int value) {
		for(int i=2; i*i<=value; i++)
			if(value%i==0)
				return false;
		
		return true;
	}
	
	public static int getDigit(int x, int y, int dir, int k) {
		int newX = x, newY = y;
		newX += k*offsetX[dir];
		newY += k*offsetY[dir];
		
		if(newX<0||newX>=array2d.length||newY<0||newY>=array2d.length)
			return -1;
		return array2d[newY][newX];
	}
	
	public static int computeValue(int x, int y, int dir, int length) {
		int value = 0;
		
		for(int len=0; len<=length; len++) {
			int digit = getDigit(x, y, dir, len);
			
			if(digit==-1)
				return -1;
			value = value*10+digit;
		}
		
		return value;
	}
	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		ArrayList<Integer> primNumber = new ArrayList<>();
		
		System.out.print("배열 사이즈 입력:");
		int size = scan.nextInt();
		array2d = new int[size][size];
		
		for(int i=0; i<size; i++)
			for(int j=0; j<size; j++)
				array2d[i][j] = scan.nextInt();
		
		for(int x=0; x<size; x++) {
			for(int y=0; y<size; y++) {
				for(int dir=0; dir<8; dir++) {
					for(int length=0; length<=size; length++) {
						int value = computeValue(x, y, dir, length);
						
						if(value!=-1&&isPrim(value)&&value!=1&&primNumber.contains(value)==false)
							primNumber.add(value);
					}
				}
			}
		}
		
		primNumber.sort(Comparator.naturalOrder());
		System.out.println("소수는 다음과 같다.");
		for(int i=0; i<primNumber.size(); i++)
			System.out.printf("소수[%d]: %d\n", i, primNumber.get(i));
	}
}

• offsetX, offsetY 배열은 방향에 따른 x값과 y값의 변화를 단위 크기로 표현한 것이며, dir 값을 통해 x값과 y값의 변화 값을 얻은 뒤, 길이(len) 만큼 곱하면 보다 손쉽게 새로운 원소의 위치(newX, newY)를 얻을 수 있다.
• array2d 2차원 배열을 main 메소드 밖, 클래스 내에서 선언함으로서 전역 변수 역활 수행하게 되며, 이로 인해 추가적으로  computeValue 메소드나 getDigit 메소드로 정보를 필요가 없어진다.
• 이번 문제는 문제의 접근 방법과 기능을 메소드 별로 효율적으로 나누는 방법, 소수 판별법, 숫자들을 합치는 방법을 필요로 하는 문제였다.