.programmers(소수 찾기)

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

 

1. 2022.04.09 시도

소요시간: 14분

import java.util.*;

class Solution {
    Set<Integer> answerSet = new HashSet<>();
    public int solution(String numbers) {
        boolean[] visited = new boolean[numbers.length()];

        recursion(numbers.toCharArray(), visited, "");

        return answerSet.size();
    }

    private void recursion(char[] numbers, boolean[] visited, String text) {
        if ("".equals(text) == false) {
            int number = Integer.parseInt(text);
            if (isPrime(number)) {
                answerSet.add(number);
            }
        }

        for (int i=0; i<numbers.length; i++) {
            if (visited[i]) {
                continue;
            } else {
                visited[i] = true;
                recursion(numbers, visited, text + numbers[i]);  
                visited[i] = false;
            }
        }
    }

    private boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }

        for (int i=2; i<num; i++) {
            if (num%i == 0) {
                return false;
            }
        }

        return true;
    } 
}

풀이 접근 과정

일단 소수 구하는 메소드를 하나 만들어둔다.

모든 조합을 만들어야하므로 recursion 아니면 iterative하게 풀 수 있는데 이번엔 recursion하게 풀었다.

Set을 이용해 중복 숫자를 제거했다.

 

느낀점

• 완전 탐색은 가끔 의문이 들 정도로 단순하다. 이게 최선이겠지?

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형