순열 (프로그래머스 : 소수 찾기)

📍 순열

---

• 서로 다른 n개 중 r개를 뽑는 경우의 수
  예를 들어 1, 2 가 있다면, 1, 2, 1, 2, 2, 1 가 있을 수 있는데
  1, 2, 2, 1 를 서로 다른 집합으로 본다! ➡ 순서 O

✔ visited 배열을 이용한 코드

static int N, R, input[], result[];
static boolean visited[];
	private static void perm(int idx) {
		if(idx == R) {
			// 문제에 따른 코드 구현
			return;
		}

		for (int i = 0; i < N; i++) {
			if(!visited[i]){
				result[idx] = input[i];
                
				visited[i] = true;
				perm(idx + 1);
				visited[i] = false;
			}
		}

	}

✔ 문제 응용 예시

- 프로그래머스 : 소수 찾기
➡ 저번 포스팅했던, 소수찾기 알고리즘 응용

import java.util.*;
class Solution {
    static int answer, N;
    static List<Integer> list;
    static String[] input;
    public int solution(String numbers) {        
        answer = 0;
        N = numbers.length();
        list = new ArrayList<>();
        input = numbers.split("");
        boolean[] visited = new boolean[N];
        String[] result;        

        for(int i = 1; i <= numbers.length(); i++) {
            result = new String[i];
            go(result, visited, i, 0);
        }
        return answer;
    }

    static void go(String[] result, 
                   boolean[] visited, int R, int idx) {
        if(idx == R) {
            int res = get(result);

            // 소수 판별 & 존재 여부
            if(isPrime(res) && !list.contains(res)) {
                list.add(res);
                answer++;
            }

            return;
        }

        for(int i = 0; i < N; i++) {
            if(!visited[i]) {
                result[idx] = input[i];

                visited[i] = true;
                go(result, visited, R, idx + 1);
                visited[i] = false;
            }
        }

    }

    static int get(String[] result) {
        String res = "";
        for(String r : result) {
            res += r;
        }
        return Integer.parseInt(res);
     }

    static boolean isPrime(int res) {
        if(res < 2) return false;
        if(res == 2) return true;

        for(int i = 2; i <= Math.sqrt(res); i++)
            if(res % i == 0) return false;
        return true;
    }
  
}