[Programmers] 고득점 Kit - Brute Force : 소수찾기 #42839

문제 링크

소수찾기

문제 조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0 ~ 9 까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
• 종이 조각으로 만들 수 있는 소수가 몇 개인지 알아내야 합니다.

변수 설명

• numbers : 각 종이 조각에 적힌 숫자가 적힌 문자열 (매개변수)
• func : numbers에서 만들 수 있는 수를 구하는 함수
• hs : func에서 만들어진 수를 담는 hashset

코드 설명

Set <Integer> hs = new HashSet<Integer>();
int answer = 0;
func("", numbers);

• numbers로 만들 수 있는 수를 hs에 넣어줍니다.

public void func(String s, String number) {
        if (number.length() == 0) {
            if(!s.equals(""))
                hs.add(Integer.parseInt(s));
        } else {
            for (int i = 0; i < number.length(); i++) {
                func(s + number.charAt(i), number.substring(0,i) + number.substring(i+1, number.length()));
                if(!s.equals(""))
                    hs.add(Integer.parseInt(s));
            }
        }
    }

• 재귀함수로 모든 수를 찾아냅니다.
• 예를 들어 처음 numbers가 "031"라고 생각해봅시다.
  

  

• 즉, 0, 3, 1, 30, 31, 10, 13, 301, 310, 103, 130이 hs에 들어가게 됩니다.

for (Iterator i = hs.iterator(); i.hasNext(); ) {
            int val = (Integer) (i.next());
            if (val == 1 || val == 0) continue;
            boolean flag = false;
            for (int num = 2; num <= Math.sqrt(val); num++) {
                if (val % num == 0) {
                    flag = true;
                    break;
                }
            }
            if (flag)
                continue;
            answer++;

        }

• hs에 있는 값이 소수인지 검사해줍니다.

문제 해답

import java.util.*;
import java.lang.Math;

class Solution {
    Set <Integer> hs = new HashSet<Integer>();
    public int solution(String numbers) {
        int answer = 0;
        func("", numbers);
/*        for(Iterator i = hs.iterator(); i.hasNext();) {
            System.out.println(i.next());
        }*/
        for (Iterator i = hs.iterator(); i.hasNext(); ) {
            int val = (Integer) (i.next());
            if (val == 1 || val == 0) continue;
            boolean flag = false;
            for (int num = 2; num <= Math.sqrt(val); num++) {
                if (val % num == 0) {
                    flag = true;
                    break;
                }
            }
            if (flag)
                continue;
            answer++;

        }
        return answer;
    }
    public void func(String s, String number) {
        if (number.length() == 0) {
            if(!s.equals(""))
                hs.add(Integer.parseInt(s));
        } else {
            for (int i = 0; i < number.length(); i++) {
                func(s + number.charAt(i), number.substring(0,i) + number.substring(i+1, number.length()));
                if(!s.equals(""))
                    hs.add(Integer.parseInt(s));
            }
        }
    }
}