[프로그래머스] 소수 찾기

소수 찾기

https://campus.programmers.co.kr/tryouts/140903/challenges

 

문제 파악

순열 문제. 가장 효율적인 방법을 찾아보자.

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

 

접근 방법

💡 permutations 문제와 비슷하지만, curr가 특정 길이 충족되면 result에 추가했던 것과 달리, 가는 도중에 보일 때마다 result에 curr값 추가한다.

즉, 길이는 정해지지 않았고 길이가 어떻든 조건 만족하면 리스트에 추가.

base case는 카운트되는 것으로 변경

• 소수 구하는 함수는 isPrime() 으로 별도로 선언한다. (리턴 bool값)
• 리스트에 다 담아두고 카운트할 수도 있지만, 본인은 담으면서 카운트 할 예정 </aside>

 

코드 구현

import java.util.*;
class Solution {
    int count=0;
    public int solution(String numbers) {
        boolean[] visited = new boolean[numbers.length()];
        backtrack(numbers,new ArrayList<>(),visited,"");
        return count;
    }
    public void backtrack(String numbers,List<Integer> curr,boolean[] visited,String s){
        if(s.length()!=0){
            int x = Integer.parseInt(s);
            if(!curr.contains(x) && isPrime(x)){
                curr.add(x);
                System.out.println(curr.toString());
                count++;
            }
        }
        //recursive call
        for(int i=0;i<numbers.length();i++){
            if(visited[i]) continue;
            visited[i] = true;
            backtrack(numbers,curr,visited,s+numbers.charAt(i));
            visited[i] = false;
        }
    }

    public boolean isPrime(int n){
        if(n<2) return false;
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0) return false;
        }
        return true;
    }
}

 

배우게 된 점

-문자열 초기화 문제 “왜 누적X??”

• s 문자열을 루프 내부에서 초기화하지 않음
• 각 재귀 호출에서 새로운 문자열을 생성하여 전달한다.

⇒ s와 numbers.charAt(i)의 값을 결합한 새로운 문자열 생성

⇒ 새로운 문자열을 생성하고, 원래의 s는 변경X ⇒ 상태 유지