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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기 | 프로그래머스

나의 풀이

우선 문제를 보고 흩어진 숫자조각으로 조합 가능한 모든 숫자를 찾는 로직을 찾아야 된다고생각했다...

 

고민하다가 머리가 너무 아플것 같아서.. 조합을 찾지않고 가능한 방법을 선택하였다.

 

먼저 주어진 숫자 조합의 최대 값 이하의 소수를 구해준다.

		for ( int i = 2 ; i <= max; i++  ) {
			if ( visits[i] == 1 ) continue;
			for ( int j = 2*i; j <= max ; j+=i) {
				visits[j] = 1;
			}

 

구한 소수 중에서 흩어진 숫자에 없는 숫자가 포함되어있는 소수가 있으면 제외시켜준다.

			// 소수를 1차적으로 거른다. 흩어진 numbers에 해당되지 않는 값을 가지고있다면 처리대상이아니다.
			String[] iS = String.valueOf(i).split("");
			boolean possible = true;

			for ( int k = 0 ; k < iS.length; k++ ) {
				if ( !numbers.contains(iS[k])) {
					possible = false;
					break;
				}
			}

 

마지막으로 숫자가 포함되어있어도, 주어진 수보다 더 많은 숫자가 사용 된 경우가 있으면 제외시켜주었다.

ex) 흩어진 수 : 71일때, 11은 1이 두번나와서 흩어진 조각으로 완성시킬 수 없는 숫자이다.

			// 2차적으로 거른다. 흩어진 수보다 더 많은 수를 가지고있는 경우를 체크한다.
			StringBuilder temp = new StringBuilder(numbers);
			
			for ( int r = 0 ; r < iS.length; r++ ) {
				int index = temp.indexOf(iS[r]);
				if ( index == -1 ) {
					possible = false;
					break;
				}
				else temp.setCharAt(index, '#');
			}

 

코드

package Programmers.Level2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FindSosuLevel2 {

	public static void main(String[] args) {

		String n = "011" ;

		int result = solution(n);

		System.out.println(result);

	}//main

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

		String[] nums = numbers.split("");

		Arrays.sort(nums,Collections.reverseOrder());

		String arrayNumber ="";

		for ( String num : nums ) {
			arrayNumber+=num;
		}

		int max = Integer.valueOf(arrayNumber);

		int[] visits = new int[max+1];

		List<Integer> prime = new ArrayList<Integer>();

		// 소수 체크. 0이면 소수다.
		for ( int i = 2 ; i <= max; i++  ) {
			if ( visits[i] == 1 ) continue;
			for ( int j = 2*i; j <= max ; j+=i) {
				visits[j] = 1;
			}

			// 소수를 1차적으로 거른다. 흩어진 numbers에 해당되지 않는 값을 가지고있다면 처리대상이아니다.
			String[] iS = String.valueOf(i).split("");
			boolean possible = true;

			for ( int k = 0 ; k < iS.length; k++ ) {
				if ( !numbers.contains(iS[k])) {
					possible = false;
					break;
				}
			}
			// 2차적으로 거른다. 흩어진 수보다 더 많은 수를 가지고있는 경우를 체크한다.
			StringBuilder temp = new StringBuilder(numbers);
			
			for ( int r = 0 ; r < iS.length; r++ ) {
				int index = temp.indexOf(iS[r]);
				if ( index == -1 ) {
					possible = false;
					break;
				}
				else temp.setCharAt(index, '#');
			}
			if ( possible ) prime.add(i);
		}

		answer = prime.size();

		return answer;
	}

}//class

제출 결과