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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

특정 범위의 소수를 구하는 에라토스테네스의 채와 조합을 응용하는 문제입니다.

 

우선 세가지 수를 뽑아 나올수 있는 합의 범위는 3000입니다.

매번 합을 구해 소수인지 판별하는것 보다 미리 소수를 구해놓고 비교하는게 더 빠릅니다. 특정 범위안의 모든 소수를 구하는 방법으론 에라토스테네스의 채가 있습니다. 이를 활용해서 3000이하의 모든 수에 관해 소수 여부를 미리 구해놓습니다.

 

다음으론 더할 세가지 수를 뽑습니다. 순서와 상관없이 합을 구하기 때문에 조합을 응용해 구하면 됩니다.

이번 경우에는 뽑아야할 수가 3개로 정해져 있으므로 3중 for문을 사용해도 구현이 가능합니다.

 

더보기

조합응용으로 구현

 

import copy

def solution(nums):

    def sumCombination(combination):
        return combination[0] + combination[1] + combination[2]

    def makeCombination(list, idx, count):
        if(count == 3):
            combinationList.append(copy.deepcopy(list))
            return
        
        for i in range(idx,len(nums)):
            list[count] = nums[i]
            makeCombination(list, i+1, count+1)


    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2,3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    combinationList = []
    primeNumber = makePrimeNumber()
    makeCombination([0]*3, 0, 0)
    answer = 0
    for i in combinationList:
        sum = sumCombination(i)
        if(primeNumber[sum] == 0):
            answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))

 

더보기

3중 for문으로 구현

def solution(nums):

    def makePrimeNumber():
        number = [0 for i in range(3_001)]
        number[1] = 1
        for i in range(2, 3_001):
            if(number[i] == 0):
                j = i * 2
                while(j < 3_001):
                    number[j] = 1
                    j += i
        return number

    primeNumber = makePrimeNumber()
    answer = 0

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                sum = nums[i] + nums[j] + nums[k]
                if(primeNumber[sum] == 0):
                    answer += 1
            
    return answer


nums = [1,2,7,6,4]
print(solution(nums))
728x90
저작자표시 비영리 변경금지

'🔍 알고리즘 > 프로그래머스 Python' 카테고리의 다른 글

[Python] 프로그래머스 49189.가장 먼 노드 (Lv.3)  (0) 2022.08.02
[Python] 프로그래머스 42576.완주하지못한선수 (Lv.1)  (0) 2022.07.18
[Python] 프로그래머스 81301.숫자문자열과영단어 (Lv.1)  (0) 2022.07.11
[Python] 프로그래머스 72410.신규아이디추천 (Lv.1)  (0) 2022.07.11
[Python] 프로그래머스 67256.키패드누르기 (Lv.1)  (0) 2022.07.11

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRuoqCKkE0DFAXt 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

넓은 범위의 소수를 모두 구하는 '에라토스테네스의 채'를 응용한 문제입니다.

에라토스테네스의 채를 구현하는 방법을 알면 큰 어려움 없이 풀이할 수 있습니다.

이번 문제처럼 여러번 소수를 사용하는 문제에서도 필요한 범위의 소수를 미리 구해놓고 정답체크를 진행하면 매번 새로 소수를 구하는 것보다 좋은 성능을 얻을 수 있습니다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q4698Re_SWEA_테네스의특별한소수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		int[] arr = new int[1_000_001];

		arr[1] = 1;

		for (int i = 2; i <= 1_000_000; i++) {
			if (arr[i] == 0) {
				for (int j = i * 2; j <= 1_000_000; j += i) {
					arr[j] = 1;
				}
			}
		}

		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			int D = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int cnt = 0;

			for (int i = A; i <= B; i++) {
				if (arr[i] == 0) {
					if (String.valueOf(i).contains(String.valueOf(D))) {
						cnt++;
					}
				}
			}

			sb.append("#").append(t).append(" ").append(cnt).append("\n");
		}

		System.out.println(sb);
	}
}
728x90
저작자표시 비영리 변경금지

'🔍 알고리즘 > SWEA' 카테고리의 다른 글

[Java] SWEA 4008.숫자만들기 (모의SW테스트)  (0) 2022.07.12
[Java] SWEA 5656.벽돌깨기 (모의SW테스트)  (0) 2022.07.11
[Java] SWEA 3234.준환이의 양팔저울 D4  (0) 2022.07.04
[Java] SWEA 7699.수지의 수지맞는 여행 D4  (0) 2022.07.04
[Java] SWEA 8382.방향전환 D4  (0) 2022.07.03

+ Recent posts

티스토리툴바