프로그래머스 - 소수 찾기

문제 링크 ▶︎ 프로그래머스 소수 찾기

문제 파악

numbers String을 각각 int로 만든 다음에 int로 구현을 할 것이냐? 아니면 문자열을 문자로 그대로 수행하고 나중에 int로 바꿀 것이냐 에 대한 선택이 필요할 것 같다.

문자열로 다룬다면 문자열의 변화가 잦을 것이기 때문에 StringBuilder를 쓰는 것이 좋아보인다.

소수를 찾아야하기 때문에 isPrime함수 역시 만들어서 써야할 것 같다.

그리고 1 와 01 은 같은 정수이기 때문에 문자열 숫자를 각각 쪼개서 만든 숫자의 중복을 제거해야하므로 HashSet도 필요할 것 같다.

정리해보면 numbers String을 하나씩 쪼개서 만들 수 있는 문자열로 모두 만들고나서 이것을 정수로 형변환해서 HashSet에 집어넣으면 중복이 제거된 정수들로만 모인 Set이 될 것이고 이거를 소수판별하면 갯수가 나올 것 같다.

접근 방법

1. 전역변수로 HashSet set을 선언하고 방문을 체크하는 check 불린 배열을 선언한다.
   그리고 solution 함수에서는 정답을 의미하는 answer를 0으로 초기화하고 set을 HashSet으로 만들어둔다.
   또한 전역 불린 배열 check도 길이가 numbers의 길이와 같게 만들어준다.

2. 또한 문자열이 자주 변동되므로 StringBuilder sb를 만들고 i=1 부터 반복문을 돌면서 dfs 함수를 수행하는데, 여기서 i=1부터 하는 이유는 여기서 i가 의미하는게 i자리수 숫자를 만드는 것이기 때문에 0자리 숫자는 필요없으니 1부터 시작해서 전체길이까지 반복한다.

3. 이렇게 dfs함수에서 깊이 dep, numbers, check, 몇자리 수를 만들것인지의 k, sb 를 인자로 건네받고, 종료조건은 dep이 만들고자하는 k자리 수를 만족하면 종료해주는데, 이때 set에다가 sb를 정수로 변환해서 넣어준다.
   그 이유는 set에 넣어야 017 과 17이 같다는 것을 알기때문이다.

4. 이후에 재귀 구현 부분을 보면, numbers 를 전체 돌면서 각 자리 문자를 c 로 추출한다. 그리고 해당 인덱스에 방문한 적이 없다면 방문처리를 해주고 문자열에 c를 추가하고 다음 재귀함수를 dep+1 해서 보내준다. 그리고 다시 돌아오면 sb에서 c를 다시 빼주고 방문처리를 다시 false로 바꿔준다.
   이렇게 하면 중복 방문도 안하게 되고, 문자열이 자주 변해도 스트링빌더로 해서 괜찮다고 생각했다.

5. dfs를 모두 수행하고 나면 set에는 String number에서 만들수있는 정수값이 모두 담겨있는데 이걸 하나씩 뽑아서 isPrime함수를 돌려서 소수인 숫자가 몇개있는지 체크하면 된다.

6. 그런데 이때 isPrime에서 if(x != 2 && x % i == 0) 2는 소수이기때문에 2를 빼고 계산해줘야 제대로된 정답이 나왔다. 이걸 못찾아서 시간을 5분은 허비한 것 같다.

코드 구현

import java.util.*;
class Solution {
    public Set<Integer> set;
    public boolean[] check;
    public boolean isPrime(int x) {
        for(int i=2; i<Math.sqrt(x)+1; i++) {
            if(x != 2 && x % i == 0) {
               return false;
            }
        }
        return true;
    }
    public void dfs(int dep, String numbers, boolean[] check, int k, StringBuilder sb) {
        if(dep == k){
            set.add(Integer.parseInt(sb.toString()));
            return;
        }
        for(int j=0; j<numbers.length(); j++){
            char c = numbers.charAt(j);
            if(!check[j]) {
                check[j] = true;
                sb.append(c);
                dfs(dep+1,numbers,check,k,sb);
                sb.deleteCharAt(sb.length()-1);
                check[j] = false;
            }
        }
    }
    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        check = new boolean[numbers.length()];
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=numbers.length(); i++){
            dfs(0,numbers,check,i,sb);
        }
        for(Integer num : set) {
            if(num > 1 && isPrime(num)){
                answer++;
            }
        }
        return answer;
    }
}

개선 사항

아이디어는 보통의 백트래킹과 동일했다. 어떻게 어떻게 풀어야겠다 라는 생각이 바로 들었지만 막상 풀어내는 시간은 꽤 오래걸린 문제이다.

구현에 있어서 StringBuilder 도 쓰고 HashSet도 쓰고 여태껏 배웠던 자료구조를 사용하면서 백트래킹 재귀를 쓰게 되어 공부가 더 잘된 것같다.

그리고 다 풀었다고 생각했는데 계속 답이 틀렸어서 dfs함수에서 뭐가 틀렸나를 계속 체크했는데 그게 아니라 2가 소수가 아닌걸로 나와서 그 부분을 고치니 정답이 되었다. 코드의 전반적인 부분을 침착하게 리뷰하는 버릇을 들여야겠다.