Coding 공부

import sys
input = sys.stdin.readline
def get_prim_number(input_Num):
    last_num = input_Num
    visited = [False for _ in range(last_num+1)]
    visited[0] = True
    visited[1] = True
 
    result = []
    for num in range(2,last_num+1):
        if not visited[num]:
            result.append(num)
            for new_num in range(2*num,last_num+1,num):
                visited[new_num] = True
    return result
N = int(input())
 
arr = list(map(int,input().split()))
result = []
max_num = max(arr)
prim_set = get_prim_number(max_num)
for val in arr:
    if val in prim_set:
        result.append(val)
 
if len(result)>0:
    answer = 1
    result = set(result)
    for prim in result:
        answer*=prim
    print(answer)
else:
    print(-1)

이 문제는 소수를 구하고, 소수가 있으면, SET에 추가를 해주고,

전부 판별을 한 뒤에, 

아무것도 없으면 -1 을,

그리고 최소공배수를 출력해주면 된다.

이 문제에서 많이 틀렸던 이유는

중복되는 소수가 온다는걸 깜빡했었다.

즉 2 2 3 5 7 이라하면, 전체를 그냥 곱하기만 하면, 420이 된다.

그러나 실제 최소공배수는 210이므로,

이러한 점을 주의하기만 하면 되는 문제였다.

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = True
    result = []
 
    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    
    return result
 
 
N = int(input())
 
prime_list = get_prim_number(N)
prefix_sum = prime_list[:]
for i in range(len(prime_list)-1):
    prefix_sum[i+1] += prefix_sum[i]
 
prefix_sum = [0] + prefix_sum
 
 
cnt = 0
left = 0
right = 0
while right <len(prefix_sum):
    temp = prefix_sum[right] - prefix_sum[left]
 
    if temp == N:
        cnt += 1
        right += 1
    elif temp < N:
        right += 1
    else:
        left += 1
        if temp == 0:
            left = right
 
print(cnt)

먼저 주어진 N까지의 소수들을 전부 구해준다.

그리고 구한 소수들을 prefix_sum으로 구간합을 구해준다.

두 포인터를 해주면 된다.

import math
import sys
 
input = sys.stdin.readline
 
def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = False
    result = []
 
    for num in range(2,int(math.sqrt(N))+1):
        if prime_check[num]:
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
    return result
 
 
N = int(input().strip())
 
prime_list = get_prim_number(N)
interval_sum = 0
left = 0
cnt = 0
for right in range(len(prime_list)):
    interval_sum += prime_list[right]
 
    while interval_sum > N:
        interval_sum -= prime_list[left]
        left += 1
 
    if interval_sum == N:
        cnt += 1
 
print(cnt)

위와 다른점은 소수를 구할때, 루트(N)까지만 반복을 해주는것과,

누적합을 미리 안 구하고, 앞에서부터 하나씩 더해가면서 right를 옮겨주고, N을 넘어가면 left를 늘려가면서 N인 경우를 찾아 주는 것이었다.

def find_prime_number():
    global N
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False
 
    for num in range(2,N+1):
        if numbers[num]:
            for num_multi in range(num*2,N+1,num):
                numbers[num_multi] = False
    prime_number = []
    for num in range(N+1):
        if numbers[num]:
            prime_number.append(num)
    return prime_number
 
 
 
N = int(input())
 
 
prime_numbers = find_prime_number()
DP = [0]*40001
 
 
 
DP[0] = 1
for prime_number in prime_numbers:
    for num in range(prime_number,N+1):
        DP[num] = (DP[num]+DP[num-prime_number])%123456789
 
 
print(DP[N])

def check(num):
    visited_numbers = set()
    visited_numbers.add(num)
    if visited[num] == 1:
        return True
    elif visited[num] == 0:
        return False
 
    while num >= 0:
        temp = 0
        copy_num = num
        while copy_num>0:
            calc_num = copy_num%10
            next_num = copy_num//10
            temp = temp + calc_num**2
            copy_num = next_num
        num = temp
        if temp == 1:
            for vi_num in visited_numbers:
                visited[vi_num] = 1
            return True
        elif temp not in visited_numbers:
            visited_numbers.add(temp)
        else:
            for vi_num in visited_numbers:
                visited[vi_num] = 0
            return False
        
 
 
def find_prime_number(N):
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False
    prime_list = []
    for num in range(2,N+1):
        if numbers[num]:
            prime_list.append(num)
            for not_prime in range(num+num,N+1,num):
                numbers[not_prime] = False
    return prime_list
 
 
 
 
N = int(input())
 
 
prime_numbers = find_prime_number(N)
 
visited = [-1]*1000001
result = []
 
for num in prime_numbers:
    if check(num):
        result.append(num)
for row in result:
    print(row)

import sys
 
input = sys.stdin.readline
def findprimenumber():
    global prime_number
    prime_number[1] = False
    prime_number[0] = False
    for i in range(2,10001):
        if prime_number[i]:
            for j in range(i+i,10001,i):
                prime_number[j] = False
 
 
 
 
 
T = int(input())
prime_number = [True]*10001
findprimenumber()
for _ in range(T):
    A,B = map(int,input().split())
    result = 'Impossible'
    visited = [-1] * 10001
    if A == B:
        print(0)
    else:
        stack = [A]
        cnt = 0
        while stack:
            new_stack = []
            for number in stack:
                number_list = list(map(int,list(str(number))))
                for ind in range(4):
                    if ind == 0:
                        for k in range(1,10):
                            if number_list[ind] != k:
                                new_number = k*1000 + 100*number_list[1] + 10*number_list[2] + number_list[3]
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
                    else:
                        for k in range(10):
                            if number_list[ind] != k:
                                new_number = number - number_list[ind]*(10**(3-ind)) + k*(10**(3-ind))
                                if visited[new_number] == -1 and prime_number[new_number]:
                                    visited[new_number] = cnt+1
                                    new_stack.append(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = new_stack[:]
            cnt += 1
        print(result)
        
        

문제는 소수를 구하는 것과 BFS를 활용하면 되는 문제였다.

먼저 자신만의 방법으로 문제에서 주어진 10000 까지의 소수를 구한다.

나는 단순하게 반복문을 통해서 구했고, True False로 구분이 되게 해주었다.

이 상황에서 주어진 넘버에서 각자리 수를 변경하면서, 방문하지 않았고 소수일때에 new_stack에 넣어주는 방식으로 했다.

import sys
 
input = sys.stdin.readline
 
 
prime_number = [True]*10000
prime_number[0] = False
prime_number[1] = False
 
for k in range(2,10000):
    if prime_number[k]:
        for j in range(k+k,10000,k):
            prime_number[j] = False
 
T = int(input())
 
for _ in range(T):
    A,B = map(int,input().split())
    if A == B:
        print(0)
    else:
        visited = [True]*10000
        result = 'Impossible'
        stack = [A]
        cnt = 0
        while stack:
            new_stack = set()
            for number in stack:
                for k in [1,10,100,1000]:
                    fall_number = number - (number//k)%10*k
                    for i in range(10):
                        new_number = fall_number + i *k
                        if prime_number[new_number] and visited[new_number] and new_number >= 1000:
                            visited[new_number] = False
                            new_stack.add(new_number)
            if B in new_stack:
                result = cnt + 1
                break
            stack = list(new_stack)[:]
            cnt += 1
        print(result)

 좀 더 깔끔한 방법으로 자리수 변경을 한 방식이다. 주어진 넘버에서 바꾸고 싶은 자리수로 나눈 몫의 10으로 나눈 나머지를 구하면, 해당 자리수를 구할 수 있다. 이 방식을 이용해서, 구현했다.