[알고리즘] 프로그래머스 소수 만들기 -Summer/Winter Coding(~2018)-

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

프로그래머스

 

프로그래머스 LEVEL2의 소수 만들기 문제를 풀어봤습니다. ㅎ

 

풀이 방법은 바로 생각이나고 예외 케이스도 없어서 바로 통과할 수 있었습니다. 

 

중복된 숫자가 없는 3이상 크기의 배열에서 3개의 숫자 조합을 꺼내어(만들어) 그 합이 소수가 되는 개수를 구하는 문제였습니다.

 

 

그래서 3중 for문으로 앞에 자리부터 차례대로 모든 조합을 꺼내올 수 있게 구현했습니다.

첫번째는 0번 인덱스에서 마지막-2 인덱스까지, 두번쨰 for문은 이전 첫번째 for문 최근 인덱스에서 마지막-1 인덱스까지, 세번째 for문 에서는 최근 두번째번 인덱스에서 마지막 인덱스까지 반복문을 돌게 함으로써 모든 조합을 얻고

 

그 조합의 합을 소수를 판별하는 함수에 넣어 구현했습니다.

 

말로 하니 힘드네요 코드를 보시면 알 것 같습니다.

 

이전에 분명 소수 판별하는 문제를 푼 것 같았는데 까먹었습니다.(최대 공약수만 풀었었나..) 시간 절약을 위해 꼭 기억하도록 합시다..!

 

 

풀이는 다음과 같습니다.

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{1,2,3,4});
    }
    public static int answer = 0;
    public int solution(int[] nums) {
        int n = 0;
        for (int i=0; i<nums.length-2; i++){
            for (int j=i+1; j<nums.length-1; j++){
                for (int k=j+1; k<nums.length; k++ ){
                    isSosu(nums[i]+nums[j]+nums[k]);
                }
            }
        }
        return answer;
    }

    public void isSosu(int num){
        int i = 2;
        while (i*i<=num){
            if(num%i == 0){
                //소수아님
                return;
            }
            i+=1;
        }
        //소수
        answer++;
    }
}

 

 

코틀린으로 풀면 다음과 같습니다. 

class Solution {
    fun solution(nums: IntArray): Int {
        for (i in 0 until nums.size - 2) {
            for (j in i + 1 until nums.size - 1) {
                for (k in j + 1 until nums.size) {
                    isSosu(nums[i] + nums[j] + nums[k])
                }
            }
        }
        return answer
    }

    fun isSosu(num: Int) {
        var i = 2
        while (i * i <= num) {
            if (num % i == 0) {
                //소수아님
                return
            }
            i += 1
        }
        //소수
        answer++
    }

    companion object {
        var answer = 0
    }
}

 

알고리즘 복습하고 안드로이드도 계속 공부해야하는데 할일도 많고 꼬이는게 많아 잘 못하고 있네요 ㅠㅠ

 

댓글과 공감은 큰 힘이 됩니다.!