[프로그래머스 / Java] Lv.2 소수찾기 - 연습 문제 (1) with ChatGPT

 

📘 연습 문제 : 비밀 코드 해독

 

문제 설명

어떤 자물쇠는 숫자 버튼으로 이루어져 있으며,
버튼에 적힌 숫자들을 일부 또는 전부 사용해 순서를 바꿔 비밀 코드를 만듭니다.

비밀 코드는 앞자리에 0이 와도 허용되며,
만들어진 숫자 중 소수인 코드의 개수를 구하려고 합니다.

---

입력

• codes : 숫자로만 이루어진 문자열
  • 길이 : 1 이상 7 이하
  • 예 : "013", "17", "235"

---

출력

• 만들 수 있는 숫자 중 소수의 개수

---

예시

codes = "013"

 

💡가능한 숫자 조합

• 1자리 : 0, 1, 3
• 2자리 : 01(1), 03(3), 10, 13, 30, 31
• 3자리 : 013(13), 031(31), 103, 130, 301, 310

👉 소수 : 3, 13, 31, 103

 

➡️ 결과 : 4

---

주요 개념

개념	사용 이유
DFS	모든 순열 생성
Set	중복 숫자 제거
재귀	남은 숫자 관리
소수 판별	결과 필터링

 

👉 완전탐색 + DFS 문제의 대표 패턴

---

스스로 점검 질문

• 왜 substring(0, i) + substring(i + 1)을 쓰는가?
• 숫자가 "011"일 때 중복 제거가 없으면 무슨 일이 생길까?
• DFS 깊이는 최대 몇 단계까지 내려갈 수 있을까?

---

Code

import java.util.*;

class Solution {

    // 중복 숫자 제거를 위한 Set
    HashSet <Integer> numberSet = new HashSet<>();

    public int solution(String codes) {

        // DFS로 모든 숫자 조합 생성
        dfs("", codes);

        int count = 0;

        // 생성된 숫자 중 소수 개수 세기
        for (int num : numberSet) {
            if (isPrime(num)) {
                count++;
            }
        }

        return count;
    }

    // DFS를 이용한 숫자 조합 생성
    private void dfs(String current, String remain) {

        // 빈 문자열이 아니면 숫자로 변환해 Set에 저장
        if (!current.equals("")) {
            numberSet.add(Integer.parseInt(current));
        }

        // 남아있는 숫자들로 순열 생성
        for (int i = 0; i < remain.length(); i++) {
            dfs(
                current + remain.charAt(i),
                remain.substring(0, i) + remain.substring(i + 1)
            );
        }
    }

    // 소수 판별 메서드
    private boolean isPrime(int num) {

        // 0과 1은 소수가 아님
        if (num < 2) {
            return false;
        }

        // √num까지만 나눠보면 충분
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }
}

---

문제 링크

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

프로그래머스