0_ch4n
기계쟁이\n개발자
0_ch4n
0chn.xxx@gmail.com @0ch._.n
전체 방문자
오늘
어제

공지사항

  • All (282)
    • 🖥 CS (21)
      • 네트워크 (12)
      • 운영체제 (3)
      • 자료구조 (2)
      • Web (4)
    • 🧠 Algorithm (185)
      • [C] BOJ (93)
      • [JAVA] Programmers (91)
    • 📚 Study (69)
      • HTML&CSS (19)
      • MySQL (11)
      • JAVA (22)
      • Servlet&JSP (8)
      • Thymeleaf (2)
      • Spring (5)
      • JPA (2)
    • 📖 Book (1)
    • 📃 Certification (6)
      • 정보처리기사 (6)

인기 글

최근 글

최근 댓글

태그

  • CSS
  • 자바
  • 코딩테스트
  • kakao
  • java
  • 카카오
  • Programmers
  • 프로그래머스
  • til
  • 코테

블로그 메뉴

  • 홈
  • 태그
  • 방명록

티스토리

hELLO · Designed By 정상우.
0_ch4n

기계쟁이\n개발자

[42839번] 소수 찾기
🧠 Algorithm/[JAVA] Programmers

[42839번] 소수 찾기

2022. 8. 9. 13:28
반응형

✔️ 문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

✔️ 제한 사항

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

 

✔️ 입출력 예

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

  • 11과 011은 같은 숫자로 취급합니다.

 

✔️ 코드 구상

numbers의 각 자리를 하나의 숫자로 보고 만들 수 있는 모든 조합을 만든 후 그 조합에 대해 소수가 몇개인지 확인하는 문제이다.

dfs를 사용해서 모든 경우의 수를 구할 때마다 List에 담고 소수인지 체크해서 필터한 리스트의 size를 반환하면 될 것 같다.

 

✔️ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(String numbers) {
        int answer = 0;

        int[] arr = Arrays.stream(numbers.split("")).mapToInt(i -> Integer.parseInt(i)).toArray();
        List<Integer> list = new ArrayList<>();

        combination(list, arr, new int[arr.length], new boolean[arr.length], 0);

        list.stream().distinct();

        List<Integer> primeList = list.stream().filter(i -> i != 0 && i != 1 && isPrime(i)).distinct().collect(Collectors.toList());

        answer = primeList.size();

        return answer;
    }

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

    public void combination(List<Integer> list, int[] arr, int[] num, boolean[] visited, int depth) {
        if(depth == arr.length) {
            return;
        }

        for(int i = 0; i < arr.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                num[depth] = arr[i];
                String str = "";

                for(int j = 0; j <= depth; j++) {
                    str += num[j];
                }

                list.add(Integer.parseInt(str));
                combination(list, arr, num, visited, depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

📄 원문

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형
저작자표시 (새창열림)

'🧠 Algorithm > [JAVA] Programmers' 카테고리의 다른 글

[12900번] 2 x n 타일링  (0) 2022.08.11
[12949번] 행렬의 곱셈  (0) 2022.08.10
[1844번] 게임 맵 최단거리  (0) 2022.08.08
[17686번] 파일명 정렬  (0) 2022.08.05
[12939번] 최댓값과 최솟값  (0) 2022.08.04
    0_ch4n
    0_ch4n
    while(true) { study(); }

    티스토리툴바