취업준비/알고리즘 문제 반추

프로그래머스 - 소수 만들기

MoonTheKid 2021. 8. 18. 17:50

들어가며... 너무 복잡하게 생각하는 것도 문제가 된다.

 

알고리즘을 풀다 보면 해당 문제를 어떤 방식으로 풀어야 할지에 대한 도구를 찾게 된다.

 

이중 혹은 삼중 반복문으로 풀 수 있을까?

 

DFS 혹은 BFS를 통해서 전방위적으로 탐색한 후 최적의 값을 도출해야 할까?

 

이후 어떤 자료구조를 사용하게 되는지에 대한 질문을 거치게 된다. [ DFS는 스택, BFS는 큐 이런식... ]

 

현재 프로그래머스 사이트의 도움을 받아서 level1의 난이도를 가진 문제들을 풀어보고 있다.

 

그러다 소수 만들기라는 문제를 풀게 되었는데 꽤나 많은 고민을 준 문제 같아서 이렇게 글을 남겨본다.

 

문제에 대한 설명

 

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

내가 위의 설명을 보고 추출한 중요한 부분은 다음과 같았다.

 

1. 3개의 수를 더해야 한다는 점

 

2. 소수인 것을 판단해야 한다는 점.

 

소수에 대한 판단

 

소수에 대한 판단은 hackerRank에서 자바 공부를 하다가 얻게된 좋은 소스가 있다.

 

BigInteger 클래스의 isProbablePrime() 메서드이다. 인자로는 certainty에 대한 값을 넘겨야 하는데 대략 10의 값을 넘기면 해당 값이 소수인지에 대한 판별률이 99.9%에 가까워진다고 한다.

 

그래서 다음과 같이 소수 판별을 위한 값을 체크하는 용도로 헬퍼 메서드로 두었다.

 

// BigInteger의 인자로는 String을 넘겨야 해서 ""+sum으로 넘겼다.

 

    private boolean checkPrime(int sum) {
        return new BigInteger(""+sum).isProbablePrime(10);
    }

 

중요한 것은 3개의 수를 조합해내야 한다는 것이다. 

 

아직 BFS랑 DFS의 갈피를 잡지 못했는데 해당 문제에 BFS를 사용해야 하는 줄 알았다...

 

A4 용지에 어떻게 하면 BFS적으로 접근할 수 있을까도 고민했다.

 

그 과정에서 nums를 슬라이싱 하기 위해서 Arrays.copyOfRange()도 들여다보게 되었다.

 

이 방식으로 접근하면 코드가 엄청 방대해진다는 것이 나의 결론.

 

그렇게 30분간의 고민끝에 내린 결론은 BFS로 푸는 게 아닌 것 같다는 것이다.

 

재귀로 풀면 뭔가 어썸한 방식이 있을 것 같은데, 도저히 내 머릿속으로는 생각이 나질 않는다.

 

찾아보니 해당 문제는 for문 3겹으로 풀면되는 문제였다.

 

가끔은 너무 어렵게 접근해서 스스로의 생각을 꼬이게 만드는 게 나의 단점인 것 같다.

 

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                for(int k = j + 1; k < nums.length; k++) {
                    if(checkPrime(nums[i] + nums[j] + nums[k])) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
    
    private boolean checkPrime(int sum) {
        return new BigInteger(""+sum).isProbablePrime(10);
    }
}

아쉬움이 남는다.

 

도널드 크누스 장인의 말이 떠오른다. 

 

"섣부른 최적화가 만악의 근원이다"

 

나는 문제를 풀기도 전에 섣부르게 최적화에 도전했다. 해당 문제를 가장 최적의 알고리즘으로 푸는 방법이 무엇일까!

 

문제를 먼저 다 풀어보고 괜찮은 선택지와 도구로 개선해나가도 늦지 않았을 문제였음에도 말이다.

 

빠른 프로그램보다는 우선 안정적이고 명세서를 만족하는 좋은 프로그램 작성에 집중해야겠다.

 

이는 알고리즘에도 통용되는 말인듯 하다.

 

문제 자체보다는 문제에 대한 접근에 고찰을 남기게 해 준 좋은 문제라고 생각한다.

 

조합을 고른다는 부분에서 혹했다.

 

매일 매일 알고리즘을 풀면서 취업준비를 하고 있다. 꽤나 몰입하는 시간이 되어서 즐겁다.

 

반응형