[코딩테스트] 프로그래머스 - 소수 찾기(Java, Level2)

안녕하세요.

게으름뱅이지만 주말이라고 삘받아서 두문제나 풀었네요~

오늘만큼은 저에게 부지런쟁이라고 스스로 칭찬하고싶습니다~:D 

얼른 눕고싶네요.

 

이번에 만나볼 문제는 소수 찾기입니다.

소수찾기는 에라토스테네스..? 의체인가 그것을 사용하면 됩니다.

숫자 하나에 또 반복문넣어서 계산하는건... 실행시간안에 가능할지는 모르겠습니다.

 

일단 문제부터 만나보시겠습니다.

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

프로그래머스

 

오늘도 그렇듯 문제 → 코드 → 설명 순으로 진행해보겠습니다.

다음은 코드입니다.

 

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        List<Integer> list=new ArrayList<>();
        String[] numberString=numbers.split("");
        
        for(int i=0;i<numberString.length;i++)
            list.add(Integer.parseInt(numberString[i]));

        Collections.sort(list,Collections.reverseOrder());
                
        //해당 Max값을 구하고 Max값만큼 반복을 돌면서 소수 검색
        int max=0;
        for(int t:list)
            max=(max*10)+t;

        boolean[] sosoo=new boolean[max+1];
        //소수구하기
        for(int i=2;i*i<=max;i++)
        {
            for(int j=i*i;j<=max;j+=i)
                sosoo[j]=true;
        }
        
        for(int i=2;i<sosoo.length;i++)
        {
            if(!sosoo[i])
            {
                boolean checker=false;
                List<Integer> temp_list=new ArrayList<>(list);
               
                String[] compare_sosoo=Integer.toString(i).split("");
                                
                for(int j=0;j<compare_sosoo.length;j++)
                {                    
                    if(!temp_list.contains(Integer.parseInt(compare_sosoo[j])))
                    {
                        checker=false;
                        break;
                    }
                    else
                    {                       
                        checker=true;
                        temp_list.remove(temp_list.indexOf(Integer.parseInt(compare_sosoo[j])));
                    }                        
                }               
                if(checker)
                    answer++;
            }
        }
        
        
        
        
        return answer;
        
    }
}

① 먼저 요소들을 리스트로 만들어 저장합니다. 추후에 비교시 사용할 예정입니다.

② 그리고 List를 역순으로 정렬합니다. List를 이용해 최대숫자를 만들고 해당범위의 소수만을 구할 예정입니다.

③ 소수를 구합니다. 소수는 앞서 말씀드린것과 같이 에라토스테네스의 체를 이용해 true, false로 구분합니다.

④ 다음은 숫자 하나씩 탐색하면서 해당 숫자가 ①에서 만든 List에 있는 숫자를 포함하는지 체크합니다

    - 먼저 소수하나를 String[]으로 만들고 하나씩 탐색합니다.

    - 탐색하면서 기존에 만든 list를 복사한 temp_list를 통해 대조합니다.

    - 다르다면 빠르게 break문을 통해 다음수를 비교

    - 같다면 해당 리스트가 중복비교되지 않게 remove를 통해 제거한후 나머지 요소들도 비교합니다.

    -  구분자를 설정해 checker가 계속 true를 유지한다면 모든요소가 temp_list에 존재한다는 뜻입니다.

⑤ 요소비교가 끝난 후에도 checker가 true라면 numbers를 이용해 만든 소수라고 판단해 answer++ 를 해줍니다.

 

이상입니다.

생각하는건 금방했는데 temp_list 복사가 헤맸습니다. 

 

오늘은 여기까지입니다.

감사합니다. :D