소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- 프로그래머스 - 소수 찾기 (문제 링크)
- DFS
- 백트래킹
- 소수 판별
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
| "17" | 3 |
| "011" | 2 |
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.
문제 접근
이 문제는 주어진 숫자 조각을 이용해 가능한 모든 숫자를 만들고, 그 숫자들이 소수인지 판별하는 문제입니다. 이를 해결하기 위해 다음과 같은 접근 방식을 사용했습니다.
- 숫자 조각 조합 생성
- DFS를 이용하여 주어진 숫자 조각들을 조합하여 모든 가능한 숫자를 만듭니다.
- 각 자리 수마다 모든 조합을 생성합니다.
- 소수 판별
- 생성된 숫자가 소수인지 판별합니다.
- 소수는 1과 자기 자신만으로 나눠지는 수입니다.
- 중복 제거
- 동일한 숫자가 여러 번 생성될 수 있으므로, Set을 이용해 중복을 제거합니다.
풀이 - Java 코드
import java.util.HashSet;
import java.util.Set;
class Solution {
private boolean[] visited;
private String n;
private int depth = 1;
private Set<Integer> set = new HashSet<>();
public int solution(String numbers) {
n = numbers;
visited = new boolean[n.length()];
for (int i = 0; i < n.length(); i++) {
dfs(0, "");
depth++;
if (depth > n.length()) {
break;
}
}
return set.size();
}
private void dfs(int depth, String str) {
if (depth == this.depth) {
int number = Integer.parseInt(str);
isDecimal(number);
return;
}
for (int i = 0; i < n.length(); i++) {
if (!visited[i]) {
visited[i] = true;
dfs(depth + 1, str + n.charAt(i));
visited[i] = false;
}
}
}
private void isDecimal(int number) {
if (number <= 1) {
return;
}
if (number <= 3) {
set.add(number);
return;
}
if (number % 2 == 0 || number % 3 == 0) {
return;
}
for (int i = 5; i * i <= number; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return;
}
}
set.add(number);
}
}풀이 설명
- 숫자 조각 조합 생성
- solution 함수에서 숫자 조각을 이용해 DFS를 시작합니다.
- dfs 함수는 재귀적으로 호출되며, 각 자리 수마다 가능한 모든 숫자를 생성합니다.
- visited 배열을 이용해 각 숫자 조각의 사용 여부를 추적합니다.
- 소수 판별
- dfs 함수에서 생성된 숫자를 isDecimal 함수로 전달하여 소수인지 판별합니다.
- isDecimal 함수는 소수를 판별하고, 소수인 경우 Set에 추가합니다.
- 중복 제거
- Set을 이용해 중복된 숫자를 제거하고, 최종적으로 소수의 개수를 반환합니다.
마무리하며
- 이번 문제를 통해 DFS와 백트래킹을 활용한 문제 해결 방법을 학습할 수 있었습니다.
- 숫자 조각을 이용해 가능한 모든 조합을 생성하고, 이를 통해 소수를 판별하는 과정으로 문제를 해결해 보았습니다.
반응형
