프로그래머스 레벨1 자바 - peulogeulaemeoseu lebel1 jaba

-첫 풀이

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

        for(int i = 2; i<=n;i++){
            int temp = 0;
            answer++;
            for(int j=1;j<i;j++){
                if(temp>1) {
                    answer--;
                    break;
                }else if(i%j == 0) {
                    temp++;                   
                }
            }

        }

        return answer;
    }
}

  프로그래머스 level 1로 분류되어 있는 소수 찾기 문제이다. 처음의 생각은 반복문을 통해 2부터 n까지의 정수들을 1부터 자신 전까지 나눈 나머지가 2개 이상인 경우, 소수가 아니라고 판단하는 식으로 진행했다. 이 경우 데이터의 범위가 1,000,000이기 때문에 뒤에 나오는 테스트 케이스에서 시간 초과 및 효율성 체크에서 좋지 않은 결과를 가져왔다.

- 에라토스테네스의 체 알고리즘

  인터넷의 도움을 받아 소수를 판별하는 알고리즘인 '에라토스테네스의 체'에 대해서 처음 접하게 되었다. 알고리즘의 핵심 내용은 2부터 시작해(1은 소수가 아니므로) 자기 자신을 제외한 배수들을 모두 '체'에 걸러주면 된다.

  1. '체'로 거르기 위한 1차운 배열을 생성한다. (n+1 크기)

  2. 2부터 배수들을 모두 체크해준다. (단, 자신은 제외하고 4,6,8,10..... <= n)

  3. 다음 3의 배수들을 모두 체크해준다.

  4. 4는 앞선 2의 배수로써 체크가 되어 소수가 아니기 때문에 넘어간다. 

  이와 같은 방식으로 진행하면 결국 2,3,5,7,11 등 소수들의 배수들이 모두 걸러지게 되며 소수들만 남게 된다. 

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 1. 에라토스테네스의 체로 거르기 위한 1차원 배열.
        boolean check[] = new boolean[n+1];
        
        // 2. 2부터 n까지의 수들 중
        for(int i =2;i<=n;i++){
            // 2-1. 소수의 배수로써 걸러진 수들은 넘어가고, (4,6,8,9..... 등)
            if(check[i] == true) continue;
            // 2-2. 자신을 제외한 배수를 고려하기 위해 i+i; j<=n;j=j+i 조건으로 걸러준다.
            for(int j=i + i;j<=n;j+=i){
                check[j] = true;
            }
        }
        
        // 3. 걸러지지 않은 수 들의 개수를 카운팅.
        for(int i=2;i<=n;i++){
            if(!check[i]) {
                answer++;
            }
        }

        return answer;
    }
}

  에라토스테네스의 체 알고리즘은 넓은 범위의 데이터들 가운데 소수를 판별하는데 효과적인 알고리즘이지만, 특정 수가 소수인지 판별하는 경우는 비효율적이라고 한다. 

RATSENO

문제설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

문제풀이

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int[] answers) {
		int[] player1 = { 1, 2, 3, 4, 5 };
		int[] player2 = { 2, 1, 2, 3, 2, 4, 2, 5 };
		int[] player3 = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };

		int[] answer = new int[] {0,0,0};
		int maxNum = 0;
		
		List<Integer> countNum = new ArrayList<Integer>();
		
		for(int i=0; i<answers.length; i++) {
			if(answers[i] == player1[i%5]) {
				answer[0]++;
			}
			
			if(answers[i] == player2[i%8]) {
				answer[1]++;
			}
			
			if(answers[i] == player3[i%10]) {
				answer[2]++;
			}
		}
		
		for(int i : answer) {
			if(i > maxNum) {
				maxNum = i;
			}
		}
		
		for(int i=0; i<3; i++) {
			if(answer[i] == maxNum) {
				countNum.add(i+1);
			}
		}
		return countNum.stream().mapToInt(i->i).toArray();
    }
}

[ 문제 ]  [프로그래머스] level1. 소수 찾기 (자바 JAVA)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12921

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

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상

programmers.co.kr

# 접근 방법 및 풀이 

• 처음에 원래 알고있는 소수 찾는 코드로 풀었는데 시간효율성 다 틀려서.. 띠용?
• 인터넷 보니까 어떤 숫자가 소수인지 확인할때 그 숫자를 2부터 해당 숫자의 제곱근범위까지로만 살펴보면 된다는 걸 깨달았다. "에라토스테네스의 체"를 이해한다면 쉽게 풀 수 있다.

# 주의할 점 

• 시간 효율성 문제가 있기때문에 에라토스테네스의 체를 이용해서 풀어야한다.

JAVA 코드

효율성 틀린 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        out: for(int i = 2; i <= n ; i ++){
            for(int j = 2; j <= i/j; j++){
                if(i%j == 0)
                    continue out;
            }
            answer++;
        }
        return answer;
    }
}

효율성 통과 코드

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        out: for(int i = 2; i <= n ; i ++){
            for(int j = 2; j <= Math.sqrt(i); j++){
                if(i%j == 0)
                    continue out;
            }
            answer++;
        }
        return answer;
    }
}

REVIEW

소수 찾을때 Math.sqrt(num) 범위로 해서 풀기!