-
프로그래머스 (Level 2) - 소수 찾기Coding Test/Coding Test 문제 풀이 2022. 1. 3. 15:07
문제 설명
코딩테스트 연습 - 소수 찾기
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이
programmers.co.kr
풀이
문자열 numbers가 주어졌을 때, 각 숫자로 만들 수 있는 소수가 몇 개인지 반환하는 문제이다.
가장 간단한 방법으로 각 숫자로 만들 수 있는 모든 조합을 만든 후, 해당 숫자가 소수인 경우를 카운트하는 완전 탐색의 방식으로 문제를 해결하였다. 풀이 방법은 다음과 같다.
1. 백트래킹 방식을 사용해서 각 숫자로 만들 수 있는 모든 조합을 만든다.
2. 각 숫자가 소수인지 판별한다.
3. 해당 숫자가 소수인 경우 HashMap 자료구조에 삽입한다.
4. HashMap 자료구조의 사이즈를 반환한다.
HashMap 자료구조를 사용한 이유는 다음과 같다.
예를 들어, "011"이라는 문자열이 주어졌을 때 0, 1, 1로 만들 수 있는 숫자는 11과 011이 포함되어있다. 11과 011은 문자열로는 서로 다른 문자열이지만, 정수형으로 반환했을 경우 같은 수가 된다.
이처럼, 숫자를 조합했을 때 같은 숫자가 중복될 경우를 처리하기 위해 HashMap 자료구조를 사용하였다.
전체 소스코드
import java.io.*; import java.util.*; public class Solution04 { static String[] numbers; static boolean[] visited; static String[] arr; static Set<Integer> set = new HashSet<>(); public int solution(String input) { numbers = input.split(""); visited = new boolean[numbers.length]; for (int i = 1; i <= numbers.length; i++) { arr = new String[i]; dfs(0, i); } return set.size(); } /** 모든 조합을 탐색하는 메서드 */ static void dfs(int depth, int finish) { if (depth == finish) { String string = ""; for (String number : arr) string += number; /* 조합한 수가 소수인 경우 set 자료구조에 삽입 */ if (isPrime(Integer.parseInt(string))) set.add(Integer.parseInt(string)); return; } for (int i = 0; i < numbers.length; i++) { if (visited[i] == false) { visited[i] = true; arr[depth] = numbers[i]; dfs(depth + 1, finish); visited[i] = false; } } } /** 소수인지 판별하는 메서드 */ static boolean isPrime(int number) { if (number == 0 || number == 1) return false; if (number == 2) return true; for (int i = 2; i <= number / 2 + 1; i++) { if (number % i == 0) return false; } return true; } }
728x90'Coding Test > Coding Test 문제 풀이' 카테고리의 다른 글
프로그래머스 (Level 2) - 타겟 넘버 (0) 2022.01.05 프로그래머스 (Level 1) - 체육복 (0) 2022.01.04 프로그래머스 (Level 2) - 더 맵게 (0) 2021.12.28 프로그래머스 (Level 2) - 기능개발 (0) 2021.12.28 프래그래머스 (Level 2) - 전화번호 목록 (0) 2021.12.28