[프로그래머스] 소수 찾기 (java 풀이)

문제 링크

프로그래머스

서론

문제가 단순해 보이지만, 소수와 백트래킹에 관한 풀이 테크닉을 갖추지 못하면 쉽게 풀 수 없는 문제입니다.

혹시 소수부터 막히시는 분들은 아래 백준 문제(1929번: 소수 구하기)를 먼저 풀고 오시는 것을 추천드립니다.

1929번: 소수 구하기

백트래킹에서 막히시는 분들은 아래 백준 문제(15663번: N과 M (9))도 추천드립니다.

15663번: N과 M (9)

풀이

소수(정수론) + 백트래킹(순열)으로 풀이가 가능합니다.

1. 소수는 에라토스테네스의 체로 풀이했으며(자세한 사항은 위키피디아 참조)
2. 순열은 백트래킹으로 구현했습니다.

참고 - 시간복잡도

에라토스테네스의 체는 \(O(MAX * \log(\log(MAX))\) 의 시간복잡도를 가지며,

순열은 숫자를 선택하느냐, 하지않느냐 둘 중 하나를 매 숫자마다 선택(\(2^N\))을 매번 루프(\(N\))를 돌기 때문에,

\(O(N * 2^N)\) 의 시간복잡도를 가집니다

따라서 최종 시간복잡도는 다음과 같습니다.

\[ O(MAX * \log(\log(MAX)) + N * 2^N) \approx O(MAX * \log(\log(MAX))) \]

 

풀이 코드

import java.util.*;

class Solution {
        final int MAX = 10000000;
        boolean[] prime = new boolean[MAX]; // 소수 미리 저장
        Map<Integer, Boolean> chk; // 백트래킹 시 숫자 중복 방지용 체크 맵
        boolean[] vst; // 백트래킹 방문 배열
        int answer = 0;
        void backtracking(String numStr, String numbers) {
            int num = Integer.parseInt(numStr);
            if (!chk.containsKey(num) && prime[num]) {
                chk.put(num, true);
                answer++;
            }
            for (int i = 0; i < numbers.length(); i++) {
                if (vst[i]) continue;
                vst[i] = true;
                backtracking(numStr + numbers.charAt(i), numbers);
                vst[i] = false;
            }
        }

        public int solution(String numbers) {
            // 소수 생성(에라토스테네스의 체)
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            for (int i = 2; i * i < MAX; i++) {
                if (!prime[i]) continue;
                for (int j = i * i; j < MAX; j += i) {
                    prime[j] = false;
                }
            }

            chk = new HashMap<>();
            vst = new boolean[numbers.length()];
            Arrays.fill(vst, false);
            for (int i = 0; i < numbers.length(); i++) {
                vst[i] = true;
                backtracking(String.valueOf(numbers.charAt(i)), numbers);
                vst[i] = false;
            }

            return answer;
        }
    }

• 소수는 prime 배열에 미리 저장했습니다. 입력으로 들어오는 numbers의 최대 크기가 7이기 때문에, 8자리 수인 천만(MAX) 값까지의 소수를 미리 저장합니다.
• 이 소수를 바탕으로 백트래킹을 진행하며 문자열을 만들어서, 소수인지 아닌지를 판별하여 answer를 증가시킵니다.

배운 점

• 에라토스테네스의 체를 복습할 수 있었습니다.
• 순열을 만드는 방법을 복습할 수 있었습니다.
• char를 문자열로 변환할 때, String.valueOf(char) 메소드를 활용할 수 있다는 사실을 알게 되었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!