[프로그래머스] 소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

소수 찾기의 핵심은 숫자를 입력했을 때 나올 수 있는 조합의 수를 찾아 내는 것이다.

보통 이러한 경우의 수를 추출 해야할 때는 완전 탐색 알고리즘인 DFS를 많이 쓰게된다. 

DFS(Depth First Search)로 깊이 우선 탐색이라고 한다. 

노드와 간선으로 구성된 트리이다. 

여기서 DFS는 트리를 탐색하는 방법 중에 하나인데 이와 상반대는 개념은 BFS가 있다. 

앞으로 코테를 볼경우 이와 같이 경우의 수를 추출해야하는 경우에는 DFS가 떠오르고 코드를 작성할 수 있는 연습을 많이 해야할 듯 하다. 

특히, DFS는 스택을 활용하기 때문에 점화식과 탈출식을 잘 생각해야 할 듯하다. 

DFS와 관련된 많은 문제를 통해서 문제에 익숙해지는 노력을 해야겠다.

다음은 내가 풀었던 방식이다. 

[해결]

1) 입력된 문자열이 만들수 있는 경우의 수를 구한다.

저의 경우는 dfs를 이용해서 발생할 수 있는 경우의 수를 뽑아냈습니다.

2) 소수 여부를 판단해서 count를 한다.

package com.ji.study;

import static org.junit.Assert.assertEquals;
import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Test;

class FindPrimeTest {

	@Test
	void test() {
		
		Solution_42839 test = new Solution_42839();
		
		assertEquals(3, test.solution("17"));
		assertEquals(2, test.solution("011"));
		assertEquals(1, test.solution("2"));
		assertEquals(12, test.solution("7843"));
		assertEquals(0, test.solution("9999999"));
		assertEquals(1336, test.solution("1276543"));
		
	}

}

package com.ji.study;

import java.util.ArrayList;
import java.util.List;

public class FindPrime {

	/**
	 * 소수는 1과 자기 자신으로만 나누어지는 수임
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		String input = "1276543";
		System.out.println(solution(input));

	}

	public static int solution(String numbers) {
		int answer = 0;

		// 숫자 조합 저장 리스트
		List<Integer> makeNumber = new ArrayList<Integer>();
		List<Integer> onlyNumber = new ArrayList<Integer>();

		// input 숫자 초기화
		char[] numToArr = numbers.toCharArray();
		Integer len = numToArr.length;

		// dfs를 이용한 입력된 숫자가 조합할 수 있는 모든 경우의 수 저장
		dfs(0, initNodeValue(numToArr, len), new int[len], new boolean[len], makeNumber);

		// 중복 숫자 제거
		for (Integer num : makeNumber) {
			if (!onlyNumber.contains(num))
				onlyNumber.add(num);
		}

		// 소수인 경우
		for (Integer num : onlyNumber) {
			if (isPrimeNumber(num))
				answer++;
		}

		return answer;
	}

	public static int[] initNodeValue(char[] numToArr, Integer numLength) {
		int[] result = new int[numLength];
		for (int i = 0; i < numLength; i++) {
			String numStr = String.valueOf(numToArr[i]);
			result[i] = Integer.valueOf(numStr);
		}
		return result;
	}

	public static void dfs(int n, int[] arr, int[] result, boolean[] visit, List<Integer> makeNumber) {
		if (n == arr.length) {// 입력된 숫자 길이 만큼의 경우의 숫자들

			// 모든 경우의 숫자들에서 한자리씩 감소하는 경우의 숫자 예외 처리
			int resultLength = result.length;
			while (resultLength > 0) {
				String numStr = "";
				for (int i = 0; i < resultLength; i++) {
					numStr += result[i];
				}

				if (numStr != "")
					makeNumber.add(Integer.valueOf(numStr));

				resultLength--;
			}

		} else {

			for (int i = 0; i < arr.length; i++) {
				if (!visit[i]) {
					visit[i] = true;
					result[n] = arr[i];
					dfs(n + 1, arr, result, visit, makeNumber);
					visit[i] = false;
				}
			}

		}
	}

	public static boolean isPrimeNumber(int number) {
		boolean result = true;

		if (number == 1 || number == 0)
			return false;

		for (int i = 2; i < number; i++) {
			if (number % i == 0) { // 나누어 떨어지는 지 확인
				result = false;
				break;
			}
		}
		return result;
	}

}