내일은 알고리즘

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

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

우선 세가지 수를 뽑아 나올수 있는 합의 범위는 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))

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))

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

Lv.3치고 간단한 조합 응용문제입니다.

전체 사용자 리스트 Y개에서 불량 사용자 리스트에 대하여 대입이 가능한 X개를 뽑아 만들면 됩니다. (yCx)

조합과 다른 점은 아이디를 넣을 수 있는 경우가 제한되어 있어 사용자 Y가 아닌 불량 사용자 X에 대해 찾는다는 점입니다. 

모든 경우(Y x X)에 대하여 가능 여부를 미리 계산한 뒤, 재귀를 통해 불량 사용자 리스트마다 사용자를 대입하고 X개를 뽑았을 때 저장했습니다.

입력 데이터의 최대 사이즈가 8개이기 때문에 중복체크는 bitmask를 이용해 간단히 구현했습니다. 

가능한 리스트 최대 길이가 64이기 때문에 HashMap을 이용해도 구현이 가능할 것 같습니다. 

package programmers;

public class q64064_Programmers_불량사용자 {

	public static void main(String[] args) {
		String[] user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
		String[] banned_id = { "fr*d*", "*rodo", "******", "******" };
		System.out.println(solution(user_id, banned_id));
	}

	private static int solution(String[] user_id, String[] banned_id) {
		int answer = 0;
		boolean[] bitmask = new boolean[1 << user_id.length];

		boolean[][] possible = new boolean[user_id.length][banned_id.length];

		for (int u = 0; u < user_id.length; u++) {
			for (int b = 0; b < banned_id.length; b++) {
				boolean flag = true;

				if (user_id[u].length() != banned_id[b].length()) {
					flag = false;
				} else {
					for (int i = 0; i < user_id[u].length(); i++) {
						if (banned_id[b].charAt(i) == '*')
							continue;
						else if (user_id[u].charAt(i) != banned_id[b].charAt(i)) {
							flag = false;
							break;
						}
					}
				}

				possible[u][b] = flag;
			}
		}

		recur(possible, bitmask, 0, 0);

		for (int i = 0; i < bitmask.length; i++) {
			if (bitmask[i])
				answer++;
		}
		return answer;
	}

	private static void recur(boolean[][] possible, boolean[] bitmask, int mask, int idx) {
		if (idx == possible[0].length) {
			bitmask[mask] = true;
			return;
		}

		for (int u = 0; u < possible.length; u++) {
			if (possible[u][idx] && (mask & (1 << u)) == 0) {
				recur(possible, bitmask, mask | (1 << u), idx + 1);
			}
		}
	}
}