250x250
250x250
JinSeopKim
Hello World!
JinSeopKim
전체 방문자
오늘
어제
  • 분류 전체보기 (168)
    • Artificial intelligence (14)
      • DeepDiveToAI (3)
      • Pytorch (3)
      • Etc (8)
    • Back-end (19)
      • Spring (10)
      • JPA (9)
    • Language (24)
      • Python (3)
      • Java (11)
      • Swift (10)
    • Math (4)
      • Linear Algebra (4)
    • CodingTest (79)
      • Algolithm (12)
      • Backjoon (25)
      • Programmers (42)
    • Etc (27)
      • Book Review (3)
      • Adsp (6)
      • Life (2)
      • Docker (1)
      • odds and ends (15)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • GitHub

인기 글

태그

  • 선형대수
  • 개발
  • ADsP
  • ios
  • 자바
  • 카카오
  • AI
  • java
  • Python
  • 프로그래머스
  • SpringMVC
  • JAVA8
  • data
  • JPA
  • 알고리즘
  • 파이썬
  • 코딩테스트
  • 머신러닝
  • 문제풀이
  • uArm
  • 브루트포스
  • 구현
  • 개발자
  • BFS
  • BOJ
  • certificate
  • 백준
  • DP
  • swift
  • Front-end

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
JinSeopKim

Hello World!

[PGM_42839] 소수 찾기
CodingTest/Programmers

[PGM_42839] 소수 찾기

2022. 2. 22. 01:18
728x90
728x90

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42839

 

코딩테스트 연습 - 소수 찾기

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

programmers.co.kr

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 완전탐색, 순열

1. 문제 이해

String으로 숫자에 대한 문자열이 입력으로 주어지고, 그 문자열에 있는 숫자들을 한 글자씩 취급하여 새로운 조합의 숫자를 만들었을 때 소수인 경우를 구하는 문제이다. 

 

2. 접근방법

문제를 해결하기 위해 주어지는 숫자를 순열로 나타낼 수 있는 경우의 수를 모두 만들어주었다. 그리고 해당 숫자들을 사용할지 안할지를 재귀로 판단하여 모든 경우를 세어줄 수 있도록 해주었고, 중복되는 경우를 제거하기 위하여 집합을 사용해주었다.

 

3. 세부 해결방안

private boolean nextPermutation(int[] numbers){
    int prevIndex;
    int n = numbers.length;
    int nextIndex = n-1;
    int changeIndex = -1;

    for(int i = n-2; i >= 0; i--){
        prevIndex = nextIndex;
        nextIndex = i;

        if(numbers[nextIndex] < numbers[prevIndex]){
            changeIndex = nextIndex;
            break;
        }
    }

    if(changeIndex == -1)
        return false;

    for(int i = n-1; i > changeIndex; i--){
        if(numbers[i] > numbers[changeIndex]){
            swap(numbers, i, changeIndex);
            break;
        }
    }
    while(++changeIndex < --n){
        swap(numbers,changeIndex,n);
    }
    return true;
}

순열의 다음 위치를 찾아주는 메소드를 만들어 해결하였다. 위 메소드로 문자로 주어진 숫자들의 순열을 구해주었다.

public int recursiveCheckNumber(int[] numbers, boolean[] checked, int checkedNumber,Set<Integer> set) {
    if(checkedNumber == numbers.length){
        String number = "";
        for(int i = 0; i < numbers.length; i++){
            if(checked[i])
                number = number + numbers[i];
        }

        if(number.equals(""))
            return 0;

        if(set.contains(Integer.parseInt(number)))
            return 0;
        set.add(Integer.parseInt(number));

        if(isPrime(Integer.parseInt(number)))
            return 1;
        else
            return 0;
    }

    checked[checkedNumber] = true;
    int a = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
    checked[checkedNumber] = false;
    int b = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
    return a + b;
}

구해진 순열에 대해서도 일부를 사용하지 않는 경우에 대한 처리도 해주어야하기 때문에 재귀로 돌아가며 사용할지 안할지를 체크하였다. 이 때 집합을 사용하여 중복하여 체크하는 경우를 제거하여주었다.

 

public boolean isPrime(int number){
    if(number == 1 || number == 0)
        return false;
    for(int i = 2; i*i <= number; i++){
        if(number % i == 0)
            return false;
    }
    return true;
}

소수를 구하는 방법은 $O(√n)$의 방법을 사용해주었다. 소수는 $√n$까지만 확인해주면 되기 때문에 위 처럼 구현하여 n번 반복이 아닌 √n까지만 확인할 수 있도록 하였다.

구현코드

package pgm_42839;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int solution(String numbers) {
        int[] permutation = new int[numbers.length()];
        for(int i = 0; i < permutation.length; i++)
            permutation[i] = i;

        int count = 0;
        Set<Integer> set = new HashSet<>();
        do{
            int[] inputNumbers = new int[numbers.length()];
            for(int i = 0; i < permutation.length; i++){
                inputNumbers[i] = numbers.charAt(permutation[i]) - '0';
            }
            boolean[] checked = new boolean[numbers.length()];
            count += recursiveCheckNumber(inputNumbers,checked,0,set);
        }while (nextPermutation(permutation));

        return count;
    }

    private boolean nextPermutation(int[] numbers){
        int prevIndex;
        int n = numbers.length;
        int nextIndex = n-1;
        int changeIndex = -1;

        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;

            if(numbers[nextIndex] < numbers[prevIndex]){
                changeIndex = nextIndex;
                break;
            }
        }

        if(changeIndex == -1)
            return false;

        for(int i = n-1; i > changeIndex; i--){
            if(numbers[i] > numbers[changeIndex]){
                swap(numbers, i, changeIndex);
                break;
            }
        }
        while(++changeIndex < --n){
            swap(numbers,changeIndex,n);
        }
        return true;
    }

    private void swap(int[] numbers, int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }

    public int recursiveCheckNumber(int[] numbers, boolean[] checked, int checkedNumber,Set<Integer> set) {
        if(checkedNumber == numbers.length){
            String number = "";
            for(int i = 0; i < numbers.length; i++){
                if(checked[i])
                    number = number + numbers[i];
            }

            if(number.equals(""))
                return 0;

            if(set.contains(Integer.parseInt(number)))
                return 0;
            set.add(Integer.parseInt(number));

            if(isPrime(Integer.parseInt(number)))
                return 1;
            else
                return 0;
        }

        checked[checkedNumber] = true;
        int a = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
        checked[checkedNumber] = false;
        int b = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
        return a + b;
    }

    public boolean isPrime(int number){
        if(number == 1 || number == 0)
            return false;
        for(int i = 2; i*i <= number; i++){
            if(number % i == 0)
                return false;
        }
        return true;
    }
}
잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)

 

728x90
728x90
저작자표시 비영리 (새창열림)

'CodingTest > Programmers' 카테고리의 다른 글

[PGM_1844] 게임 맵 최단거리 (java)  (0) 2022.02.23
[PGM_42860] 조이스틱 (java)  (0) 2022.02.22
[PGM_42746] 가장 큰 수 (java)  (0) 2022.02.21
[PGM_42587] 프린터 (java)  (0) 2022.02.21
[pgm_64065] 튜플 (java)  (0) 2022.02.15
    'CodingTest/Programmers' 카테고리의 다른 글
    • [PGM_1844] 게임 맵 최단거리 (java)
    • [PGM_42860] 조이스틱 (java)
    • [PGM_42746] 가장 큰 수 (java)
    • [PGM_42587] 프린터 (java)
    JinSeopKim
    JinSeopKim
    기록📚

    티스토리툴바