내일은 알고리즘

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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH 

https://nodingco.tistory.com/77

Java코드와 풀이 접근방법은 위쪽 포스팅에서 확인해주세요.

class Operation:
    def __init__(self, plus, minus, multiple, divide):
        self._plus = plus
        self._minus = minus
        self._multiple = multiple
        self._divide = divide

def dfs(value, count, operation):
    global minValue
    global maxValue

    if(count == N):
        minValue = min(minValue, value)
        maxValue = max(maxValue, value)
        return
    
    if(operation._plus > 0):
        operation._plus -= 1
        dfs(value + number[count], count+1, operation)
        operation._plus += 1
    if(operation._minus > 0):
        operation._minus -= 1
        dfs(value - number[count], count+1, operation)
        operation._minus += 1
    if(operation._multiple > 0):
        operation._multiple -= 1
        dfs(value * number[count], count+1, operation)
        operation._multiple += 1
    if(operation._divide > 0):
        operation._divide -= 1
        dfs(int(value / number[count]), count+1, operation)
        operation._divide += 1

def createOperation(tempOp):
    operation = Operation(tempOp[0],tempOp[1],tempOp[2],tempOp[3])
    return operation

T = int(input())
for test_case in range(1, T + 1):
    minValue = 100_000_001
    maxValue = -100_000_001
    N = int(input())
    operation = createOperation(list(map(int, input().split())))
    number = list(map(int, input().split()))

    dfs(number[0], 1, operation)

    print("#{} {}".format(test_case, maxValue-minValue))

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

숫자카드는 고정되어 있고 그 사이에 들어갈 연산자만 정해주면 됩니다.

연산의 순서는 우리가 기존에 알던 수학과 달리 무조건 좌측부터 진행됩니다.

조금 더 효율적인 계산을 위해 연산자를 모두 정하고 나서 계산하지 않고, 재귀함수 내부에서 값을 가진 채 진행하면서 구현했습니다.

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

public class q4008_SWEA_숫자만들기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, max, min;
	static int[] num;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		int answer;
		
		for(int tc = 1; tc <= T ; tc++){
			max = Integer.MIN_VALUE; 
			min = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			num = new int[N];
			
			st = new StringTokenizer(br.readLine());
			int[] op = {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
			
			st = new StringTokenizer(br.readLine());
			for(int n = 0; n < N; n++) {
				num[n] = Integer.parseInt(st.nextToken());
			}
			
			dfs(num[0], 1, op[0], op[1], op[2], op[3]);
			
			answer = max-min;
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	static void dfs(int result, int count, int plus, int minus, int multiple, int divide) {
		
		if(count == N) {
			if(result < min) {
				min = result;
			}
			
			if(result > max) {
				max = result;
			}
		}
		
		if(plus > 0) {
			dfs(result + num[count], count+1, plus-1, minus, multiple, divide);
		}
		if(minus > 0) {
			dfs(result - num[count], count+1, plus, minus-1, multiple, divide);
		}
		if(multiple > 0) {
			dfs(result * num[count], count+1, plus, minus, multiple-1, divide);
		}
		if(divide > 0) {
			dfs(result / num[count], count+1, plus, minus, multiple, divide-1);
		}
		
	}
}

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

오늘 푼 다른 문제들과 비슷한 간단한 시뮬레이션 문제입니다.

앞에서부터 입력된 List를 쭉 읽어가면서 영어로 된 숫자가 나오면 변환하고 단어의 길이만큼 점프해 진행했습니다.

숫자가 나오면 바로 answer에 누적해주었습니다.

자릿수 문제는 앞에서부터 List를 읽어가기 때문에 새로운 숫자가 더해지기 전에 기존의 answer에 10을 곱하고 더하는 식으로 구현했습니다. 

List에 각 자릿수의 숫자를 하나씩 append하고 반복문이 끝난 후 마지막에 List를 숫자로 변환시켜도 같은 결과가 나옵니다.

def solution(s):
    answer = 0
    i = 0
    # numList = []
    while(i < len(s)):
        character = ord(s[i])
        num = 0
        if(48 <= character and character <= 57):
            num = int(s[i])
            i += 1
        else : 
            if(s[i] == 'z'): 
                num = 0
                i += 4
            elif(s[i] == 'o'):
                num = 1
                i += 3
            elif(s[i] == 'e'):
                num = 8
                i += 5
            elif(s[i] == 'n'):
                num = 9
                i += 4
            elif(s[i] == 't'):
                if(s[i+1] == 'w'):
                    num = 2
                    i += 3
                else : 
                    num = 3
                    i += 5
            elif(s[i] == 'f'):
                if(s[i+1] == 'o'):
                    num = 4
                    i += 4
                else : 
                    num = 5
                    i += 4
            else :
                if(s[i+1] == 'i'):
                    num = 6
                    i += 3
                else : 
                    num = 7
                    i += 5
        answer = answer * 10
        answer += num
        # numList.append(str(num))
    # print(numList)
    # numString = "".join(numList)
    # answer = int(numString)
    return answer

input = ["one4seveneight","23four5six7","2three45sixseven","123"]

for i in input:
    print(solution(i))

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

문자열이나 문자의 비교, 아스키코드를 알아야 쉽게 풀 수 있는 시뮬레이션 문제입니다.

입력된 문자열을 7단계를 거쳐 요구하는 조건에 맞는 문자열로 변형시켜야 하는데, 한 함수 안에서 동작해도 상관 없지만 구현시에 헷갈리지 않기 위해 7단계를 step 1~7로 쪼개어 각각 구현했습니다.

def solution(new_id):
    
    id = step1(new_id)
    id = step2(id)
    id = step3(id)
    id = step4(id)
    id = step5(id)
    id = step6(id)
    id = step7(id)

    answer = ""
    for i in id:
        answer += i
    return answer

def step1(id):
    result = []
    for i in id:
        character = ord(i)
        if(65 <= character and character <= 90):
            result.append(chr(character + 32))
        else:
            result.append(i)

    return result

def step2(id):
    result = []
    for i in id:
        character = ord(i)
        if((97 <= character and character <= 122) or (48 <= character and character <= 57) or character == 45 or character == 46 or character == 95):
            result.append(i)

    return result

def step3(id):
    result = []
    before = ''
    for i in id:
        if(before == '.' and i == '.'):
            continue
        else :
            result.append(i)
            before = i

    return result

def step4(id):
    if(len(id) > 0 and id[0] == '.'):
        id = id[1:]
    if(len(id) > 0 and id[-1] == '.'):
        id = id[0:-1]
    return id

def step5(id):
    if(len(id) == 0):
        return ['a']
    return id

def step6(id):
    if(len(id) > 15):
        id = id[0:15]
        if(len(id) > 0 and id[-1] == '.'):
            id = id[0:-1]
    return id

def step7(id):
    while(len(id) < 3):
        id.append(id[-1])
    return id


input = ["...!@BaT#*..y.abcdefghijklm","z-+.^.","=.=","123_.def","abcdefghijklmn.p"]
# input = ["...!@BaT#*..y.abcdefghijklm"]

for i in range(len(input)):
    print(solution(input[i]))

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

조금 머리를 써야하는 시뮬레이션 문제입니다.

왼손과 오른손의 엄지를 써서 누르는 방법이 정해진 번호 (1,4,7,*)과 (3,6,9,#)은 그대로 진행하면 되지만 중앙의 (2,5,8,0) 번호는 현재 상황에서 더 가까운 손가락을 사용해야 합니다.

저는 각 번호마다 해당 번호와의 거리를 미리 계산해놓고, 현재 손가락의 위치를 통해 거리를 비교하는 식으로 구현했습니다.

def solution(numbers, hand):
    distance = [[3,1,0,1,2,1,2,3,2,3,4,4],[2,2,1,2,1,0,1,2,1,2,3,3],[1,3,2,3,2,1,2,1,0,1,2,2],[0,4,3,4,3,2,3,2,1,2,1,1]]
    # 순서대로 2,5,8,0과 각 버튼(0~9,*,#)의 거리
    flag = (hand == "right")
    left = 10
    right = 11
    answer = ''

    for i in numbers :
        if(i == 1 or i == 4 or i == 7):
            left = i
            answer += 'L'
        elif(i == 3 or i == 6 or i == 9):
            right = i
            answer += 'R'
        else : 
            target = 0
            if(i == 5):
                target = 1
            if(i == 8):
                target = 2
            if(i == 0):
                target = 3
            
            if(distance[target][left] == distance[target][right]):
                if(flag) : 
                    right = i
                    answer += 'R'
                else : 
                    left = i
                    answer += 'L'
            elif(distance[target][left] < distance[target][right]):
                    left = i
                    answer += 'L'
            else : 
                    right = i
                    answer += 'R'
    return answer

numbers = [[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5],[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2],[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]]
hand = ["right", "left", "right"]

for i in range(0,3):
    print(solution(numbers[i],hand[i]))

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

프로그래머스 사이트가 리뉴얼 되었습니다.

전보다 훨씬 세련되고 보기 좋아졌습니다. 또 새로운 컨텐츠가 들어갈 페이지도 생긴것 같습니다.

파이썬을 오랜만에 쓸 겸 1 레벨 문제를 쭉 풀어봤습니다.

아주 간단한 시뮬레이션 문제입니다.

요구사항대로 입력을 탐색해서 인형을 고르고, 먼저 뽑힌 바구니의 인형과 비교해서 터트려주면 됩니다.

바구니의 구현은 Stack을 이용해도 될것 같지만 List로도 충분하고 더 간단할 것 같아서 List로 구현했습니다.

def solution(board, moves):
    answer = 0
    besket = []

    for i in moves:
        for j in range(0, len(board)):
            if(board[j][i-1] != 0):
                pick = board[j][i-1]
                # print(pick)
                board[j][i-1] = 0

                if(len(besket) > 0 and besket[-1] == pick):
                    besket = besket[0: -1]
                    answer += 2
                else : 
                    besket.append(pick)
                break
    return answer


board = [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]
moves = [1,5,3,5,1,2,1,4]
print(solution(board, moves))

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

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

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

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

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