99클럽 코테 스터디 15일차 TIL [완전탐색 - 순열]

 

- 오늘의 학습 키워드 : 완전탐색 - 순열

[문제 이름 :   소수 찾기(프로그래머스, Lv2) ]

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

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(String numbers) {
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[numbers.length()];

        getNumber(numbers, "", visited, list);
        return list.size();
    }
    
    // 모든 경우의 수 생성
    static void getNumber(String numbers, String cur, 
                          boolean[] visited, ArrayList<Integer> list) {

        if(!cur.isEmpty()) {
            int num = Integer.parseInt(cur);
            if((list.indexOf(num) == -1) && isPrime(num)) {
             list.add(num);   
            }
        }

        for(int i=0; i<numbers.length(); i++) {
            if(!visited[i]) {
                visited[i] = true;
                getNumber(numbers, cur + numbers.charAt(i), visited, list);
                visited[i] = false;
            }
        }
    }
    
    // 소수 여부 판별
    static boolean isPrime(int num) {
        if (num < 2) return false;
        
        for(int i=2; i<=Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

[풀이 과정]

1. 모든 숫자의 조합을 떠올려보아야 하므로, 순열로 문제를 풀어야 함을 먼저 떠올렸다.

2. getNumber() 메서드에서 재귀를 돌리며 숫자를 생성해낸다. 이때 cur은 현재 생성된 숫자 문자열을 의미한다. visited[] 배열은 각 문자가 사용되었는지의 여부를 추적한다.

3. 소수이면서 ArrayList에 값이 없는 숫자를 정답에 추가한다.

4. 조건이 충족된 값들만 담겨있는 ArrayList의 개수를 리턴한다.

 

순열 탐색을 재귀를 이용해서 풀이하는 과정을 구현하였다.

ArrayList가 아니라, Set을 이용해서 문제를 풀었다면 좀 더 좋은 코드가 되었을 것 같다.

풀이 시간 : 30분

 

내일은 Two Pointer, Sliding Window 알고리즘에 대해 복습해보는 시간을 가져보려 한다.

프로그래머스